18-19 თებერვალს ჩატარდა საქართველოს მოსწავლეთა ეროვნული ოლიმპიადა ინფორმატიკაში. მონაწილეები სამ ასაკობრივ ჯგუფში გადანაწილდნენ: VIII, IX-X და XI-XII კლასები.

გთავაზობთ შეჯიბრში მოცემული ამოცენების გარჩევას. მათი პირობების სანახავად კი ამ ბმულს მიჰყევით.



# ამოცანა ამოცანის ავტორი გარჩევის ავტორი
VIII კლასი ელდარ ბოგდანოვი
1 angles გიორგი მანდარია
2 prinum ზაზა გამეზარდაშვილი
3 brick ზაზა გამეზარდაშვილი
IX-X კლასი
1 illumin ზაზა გამეზარდაშვილი
2 friends გიორგი მანდარია
3 math გიორგი მანდარია
XI-XII კლასი
1 mindif გიორგი მანდარია
2 knight ზაზა გამეზარდაშვილი
3 stamps გიორგი მანდარია



VIII კლასი




ეს ამოცანა მე-8 კლასისთვის შემოთავაზებულ კრებულში ყველაზე რთული იყო და მოითხოვდა როგორც ალგორითმულ, ასევე ტექნიკურ ოპტიმიზაციებს.

დასაწყისისთვის ვახსენოთ „პირდაპირი“ ამოხსნა: მატრიცის ყოველი უჯრისთვის შეგვიძლია ავჯამოთ მის კუთხეში მყოფი უჯრების (ასეთი კი სულ არაუმეტეს 2K-1 ცალია) რიცხვები და მათ შორის მაქსიმალური ავირჩიოთ. ამ ალგორითმის მუშაობის დრო O(N2 * K) არის და მოცემულ შეზღუდვებში იგი მხოლოდ ნაწილობით ქულას იღებს.

ჩვენი ამოხსნის დასასწრაფებლად გამოვიყენოთ ე.წ. კერძო ჯამების დათვლის იდეა. მატრიცის ყოველ რიგში გამოვთვალოთ ჯამი მისი დასაწყისიდან j-ურ უჯრამდე (j = 1, 2, ..., N) და შევინახოთ თითოეული მათგანი - ვთქვათ, R[i][j] იქნება i-ურ რიგში პირველი j რიცხვის ჯამი. ადვილი დასანახია, რომ თუ ვიცით R[i][j], R[i][j + 1] მასზე 1 რიცხვის დამატებით მიიღება, კერძოდ იმის, რომელიც მატრიცის (i, j + 1) ელემენტში წერია. ამიტომ R-ის ყველა მნიშვნელობის გამოთვლა ჯამში O(N2) დროში შეიძლება. ანალოგიურად მოვიქცეთ სვეტებისთვისაც და C[i][j] იყოს j-ურ სვეტში პირველი i რიცხვის ჯამი.

ვთქვათ, R[][] და C[][] სიდიდეები უკვე გამოვთვალეთ. განვიხილოთ კონკრეტული (i, j) უჯრა. დავუშვათ, j + K ≤ N. მაშინ ამ უჯრის კუთხე შეიცავს ყველა რიცხვს (i, j + 1), (i, j + 2), ..., (i, j + K) უჯრებიდან. გავიხსენოთ, რა ჩავწერეთ R[i][j + K]-ში - ესაა ჯამი i-ური რიგის 1-დან (j + K)-მდე უჯრების რიცხვების. თავის მხვრივ R[i][j] არის ჯამი i-ური რიგის 1-დან j-მდე უჯრების რიცხვების. მათი სხვაობა ზუსტად საპოვნელ ჯამს გვაძლევს, ანუ ყველა უჯრის გადავლის ნაცვლად შეგვიძლია უკვე გამოთვლილი მნიშვნელობების საშუალებით იგი სწრაფად ვიპოვოთ. ანალოგიური მსჯელობით ვიპოვით ჯამებს სვეტებშიც და იმ შემთხვევებშიც, როდესაც i + K ან j + K აღემატება N-ს. აღწერილი ალგორითმის სირთულე არის O(N2).

ასევე მინდა გავამახვილო C++-ის მომხმარებლების ყურადღება შემოტანა-გამოტანის ოპერაციების სწრაფქმედებაზე. cin/cout ფუნქციების და ifstream/ofstream კლასების გამოყენების დროს შემოტანა და გამოტანა შედარებით ნელია, ანუ შეიძლება დიდი მოცულობის (1MB და მეტი) ინფორმაციის მიმოცვლისას ნახევარი წამიც კი წაიღოს. რა თქმა უნდა, იმ პირობებში როდესაც პროგრამამ სულ 1 წამი უნდა იმუშავოს, ეს სასურველი არაა. ამ შემთხვევებში ხელსაყრელია scanf/printf ფუნქციების გამოყენება, რომლებიც ბევრად უფრო სწრაფად უმკლავდებიან შეტანა-გამოტანას. ამ ამოცანაში ეს აუცილებელი იყო სრული ქულის ასაღებად.


გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.





ეს ამოცანა კი ყველაზე მარტივი იყო და პროგრამირების ენის უმარტივესი კონსტრუქციების ცოდნის შემოწმებას ემსახურებოდა. განვიხილოთ მისი ამოხსნის ორი მიდგომა:

ა) შევინახოთ N როგორც რიცხვი. ამ შემთხვევაში მისი ციფრების განსახილველად დაგვჭირდება while ციკლის გამოყენება, რომელიც აიღებს N-ის 10-ზე გაყოფისგან ნაშთს (ეს კი N-ის ბოლო ციფრია), დაამუშავებს მას და შემდეგ N-ს 10-ზე გაყოფს. როდესაც N 0-ის ტოლი გახდება, ციკლი მუშაობას დაამთავრებს. ციფრის დამუშავება გულისხმობ შემოწმებას, რომ იგი 2-ის, 3-ის, 5-ის ან 7-ის ტოლია, რაც ჩვეულებრივ პირობით ოპერატორ if-ით არის შესაძლებელი, და პასუხის მთვლელის გაზრდას ასეთ შემთხვევაში.

ბ) შევინახოთ N როგორ სტრიქონი. მაშინ მისი ციფრების მისაღებად უბრალოდ სტრიქონის თითოეულ პოზიციაზე მყოფი სიმბოლო უნდა განვიხილოთ. სიმბოლოების შედარება ისევე შეიძლება, როგორც რიცხვების: ამოღებულ ციფრებს ‘2’, ‘3’, ‘5’ და ‘7’ სიმბოლოებთან შევადარებდით.


გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.





ამ ამოცანაშიც შეგვიძლია ორი განსხვავებული მიდგომა გამოვყოთ:

ა) ვარიანტების გადარჩევა. გადავარჩიოთ ცალობით საყიდელი აგურების რაოდენობა A - იგი 0-დან N-მდე შუალედში არის. ფიქსირებული A-სთვის გადავარჩიოთ საყიდელი 16-აგურიანი შტაბელების რაოდენობა B - იგი [0, (N-A) div 16] შუალედში იქნება. B-ს ფიქსირებული მნიშვნელობისთვის 80-აგურიანი შტაბელების რაოდენობა უკვე ცალსახად გამოითვლება: თუ (N – A – B * 16) იყოფა 80-ზე, გაყოფის შედეგი ასეთი ტიპის შტაბელების საყიდელი რაოდენობაა, თუ არა და ასეთი A და B-თი ზუსტად N-ს ვერ შევაგროვებთ. არჩეული A, B, (N – A – B * 16) div 80 რაოდენობებისთვის გადასახდელი თანხა მარტივად გამოითვლება და ასეთი მინიმალური თანხა ამოცანის პასუხია.

ბ) ხარბი ალგორითმი. დავაკვირდეთ, რომ 16 აგურის ცალობით ყიდვას 16-აგურიანი შტაბელის ყიდვა ჯობია და ასევე 80 = 16 * 5 და 5 ცალ 16-აგურიან შტაბელზე უფრო იაფი 1 ცალი 80-აგურიანი შტაბელია. ამრიგად, უნდა ვიყიდოთ რაც შეიძლება მეტი 80-აგურიანი შტაბელი, დარჩენილი აგურები შევავსოთ რაც შეიძლება მეტი 16-აგურიანი შტაბელით და დარჩენილი არაუმეტეს 15 აგური ცალობით შევიძინოთ. ამ ლოგიკაზე დაფუძნებით გამოგვდის ძალიან სწრაფი O(1) სირთულის ალგორითმი.

გაითვალისწინეთ, რომ ეს ალგორითმი სწორია მხოლოდ იმიტომ, რომ ყოველ შტაბელში აგურების რაოდენობა წინა ვარიანტში აგურების რაოდენობის ჯერადია: 16 იყოფა 1-ზე, ხოლო 80 16-ზე. მაგალითად, რომ გვქონდეს 3- და 8-აგურიანი შტაბელები, რომელთა ფასები შესაბამისად 4 და 10 ლარია, ხოლო 1 აგურის ფასი 3 ლარი იყოს, 9 აგურის შეძენა 12 ლარად იქნებოდა შესაძლებელი (სამი ცალი 3-აგურიანი შტაბელი), მაშინ როდესაც ჩვენი ხარბი ალგორითმით ჯერ 8-აგურიან შტაბელს შევიძენდით 10 ლარად, შემდეგ კი 1 ცალ აგურს დამატებით 3 ლარად.


გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.



IX-X კლასი





ამოცანაში დაწესებული შეზღუდვები გვაძლევს საშუალებას შემდეგი „სიმულაციური“ ალგორითმისთვის. შემოვიღოთ N-ელემენტიანი მასივი, რომლის i-ურ პოზიციაზე ჩვენ ჩავწერთ 1-ს, თუ მაგისტრალის i-ური მონაკვეთი განათებულია და 0-ს წინააღმდეგ შემთხვევაში. თავიდან მასივი 0-ებით იქნება ინიციალიზირებული და ჩვენ ლამპიონების სათითაოდ განხილვის შედეგად მას ნელ-ნელა შევავსებთ. i-ური ლამპიონის განხილვისას მასივის ყველა ელემენტში [Xi – Ri, Xi + Ri) შუალედში ჩავწეროთ 1 - ამით მოვნიშნავთ, რომ მაგისტრალის შესაბამისი მონაკვეთები განათებულია. ყველა ლამპიონის განხილვის შემდეგ ჩავიაროთ ეს მასივი და დავითვალოთ, რამდენი ელემენტი მასში არის 0-ის ტოლი - ეს იქნება ამოცანის პასუხი.

თუ აღვნიშნავთ ლამპიონების განათების რადიუსებს შორის მაქსიმალურს R-ით, აღწერილი ალგორითმის სირთულე იქნება O(K * R + N) - პირველი შესაკრები ლამპიონების განხილვისთვის, მეორე კი მასივში 0-იანების დასათვლელად. სავარჯიშოს სახით გიტოვებთ ისეთი ალგორითმის მოფიქრებას, რომელიც O(K * R) დროში იმუშავებს.

როგორც ხედავთ, ეს მიდგომა მოცემულ ამოცანაში სავსებით საკმარისია სრული ქულის ასაღებად. მიუხედავად ამისა, იგი უფრო ზოგადი სახითაც შეიძლება დავსვათ: მაგალითად, არ შევზღუდოთ N და R შედარებით მცირე სიდიდეებით და ორივე არაუმეტეს მილიარდისა იყოს. მაშინ, ცხადია, ვერც მილიარდელემენტიან მასივს შემოვიღებთ და ვერც ყოველი ლამპიონისთვის „გავირბენთ“ მაგისტრალის ამ ლამპიონის შესაბამის მონაკვეთებს. ამოცანა ამ სახითაც ამოიხსნება O(KlogK) დროში. ასეთი ალგორითმის მოფიქრებასაც სავარჯიშოდ გიტოვებთ.


გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.





ამოცანის ზღაპრის მიღმა საკმაოდ სტანდარტული გრაფი იმალება: სტუდენტები გრაფის წვეროებს, ხოლო მეგობრული კავშირები კი წიბოებს წარმოადგენენ. თუ გამოვთვლით წვერო 1-დან ყოველ დანარჩენ წვერომდე უმოკლესი გზის სიგრძე და აღვნიშნავთ num[X]-ით ისეთი წვეროების რაოდენობას, რომლებამდე გზის სიგრძე X-ის ტოლია, მაშინ num[X]-ის მაქსიმალური მნიშვნელობის პოვნას გვთხოვენ. ვინაიდან გრაფი არაწონიანია, უმოკლესი მანძილების დათვლა შეიძლება BFS ალგორითმის მეშვეობით O(N+M) დროში. ალგორითმის პროცესში num[] მნიშვნელობებსაც თუ დავითვლით, შემდეგ ამოცანის პასუხს ტრივიალურად დავადგენთ ამ მასივის ერთხელ გავლით.


გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.





განვიხილოთ ამოხსნის ორი განსხვავებული მიდგომა.

ა) ხარბი ალგორითმი. განვიხილოთ პირველის გარდა ყველა რიცხვი. ლოგიკურია, რომ უფრო დიდ რიცხვებს „+“ ნიშანი უნდა მივუწეროთ, ხოლო უფრო მცირე რიცხვებს - „-“ ნიშანი. ამის დამტკიცება მარტივად შეიძლება: თუ გვაქვს ისეთი A და B რიცხვები, რომ A < B და A-ს წინ „+“ მივუწერეთ, B-ს კი „-“, მაშინ მიმდინარე გამოსახულების ჯამში ამ ორი რიცხვის წილია (A – B), ხოლო ნიშნები რომ გავუცვალოთ, იგი (B – A) იქნება და რადგან A ნაკლებია B-ზე, მეორე გამოსახულებას უფრო დიდი მნიშვნელობა აქვს.

ამ ლოგიკის იმპლემენტაცია შეიძლება O(N2) დროში, თუ მიყოლებით ვიპოვით რიცხვებს შორის მაქსიმალურს, მივუწერთ „+“-ს, თუ მათი დასმა ჯერ კიდევ შეგვიძლია და „-“-ს წინააღმდეგ შემთხვევაში და ამოვშლით ამ რიცხვს მომდევნო განხილვიდან. ასევე შეგვიძლია რიცხვები უბრალოდ დავალაგოთ (ცნობილია, რომ დალაგება O(NlogN) დროშია შესაძლებელი) და პირველი K ცალი უარყოფითად ჩავთვალოთ, დანარჩენები კი დადებითად. ორივე მიდგომაში ვგულისხმობთ, რომ განიხილება რიცხვები პირველის გამოკლებით.

ბ) დინამიური პროგრამირება. F(i, j) იყოს ისეთი გამოსახულებების მაქსიმალური შესაძლო ჯამი, რომლებიც მოცემული რიცხვებიდან პირველ i ცალს შეიცავს და მათში ზუსტად j რაოდენობის „-“ ნიშანი არის დასმული. ასევე აღვნიშნოთ მოცემული რიცხვები A1, …, AN-ით. ცხადია, F(1, 0) = A1. ასევე გვაქვს:

F(i, j) = MAX( F(i – 1, j – 1) – Ai, F(i – 1, j) + Ai ), თუ j > 0
F(i, j) = F(i – 1, j) + Ai, თუ j = 0

ამოცანის პასუხი F-ის ტერმინებში ჟღერს როგორც “ისეთი გამოსახულებების მაქსიმალური შესაძლო ჯამი, რომლებიც მოცემული N-ივე რიცხვისგან შედგება და ზუსტად K ცალ გამოკლების ნიშანს შეიცავს“, ანუ F(N, K). როგორც ხედავთ, მის გამოსათვლელად გვჭირდება მხოლოდ F(N – 1, K) და F(N – 1, K – 1) მნიშვნელობები, მათ გამოსათვლელად - F(N – 2, K), F(N – 2, K – 1) და F(N – 2, K – 2) მნიშვნელობები და ასე შემდეგ, ანუ F(i, j) მნიშვნელობებს თუ გამოვთვლით მოცემული ფორმულებით i-ს და j-ს ზრდადი მიმდევრობით (ჯერ F(2, 0), მერე F(2, 1), …, F(3, 0), F(3, 1), …), ყოველთვის უკვე გამოთვლილ მნიშვნელობებს გამოვიყენებთ.

ამ მიდგომის სირთულე O(NK) გახლავთ.


გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.



XI-XII კლასი.





ეს ამოცანა თავის კრებულში ყველაზე მარტივი იყო. მისი ამოხსნა რამდენიმენაირად შეიძლება, მაგრამ მე აღვწერ მხოლოდ ვარიანტების გადარჩევაზე დაფუძნებულ მეთოდს, რომელიც შედარებით მარტივია რეალიზაციაში ნებისმიერ პროგრამირების ენაზე.

მაშ ასე, ჩვენი მიზანია მივიღოთ ყველა შესაძლო ორნიშნა რიცხვთა წყვილი მოცემული 4 ციფრისგან და შემდეგ მათთვის გამოვთვალოთ ამოცანაში მოთხოვნილი ფუნქცია და ვიპოვოთ მისი მინიმუმი. ჩავწეროთ მოცემული ციფრები 4-ელემენტიან A მასივში და ასევე ვიქონიოთ მეორე 4-ელემენტიანი მასივი U, რომლის i-ური ელემენტი იქნება 1, თუ მოცემული 4 ციფრიდან i-ური უკვე ჩავსვით რომელიმე რიცხვში და 0 წინააღმდეგ შემთხვევაში. ჩვენი დავალების გადაჭრა ასეთ სტილშია შესაძლებელი:

For a := 1 to 4 do
begin
  U[a] := 1;
  For b := 1 to 4 do
  begin
    If U[b] then continue;
    U[b] := true;
    For c := 1 to 4 do
    begin
      If U[c] then continue;
      U[c] := true;
      d := 10 – a – b – c; // ვეყრდნობით იმას, რომ განსხვავებული ინდექსების ჯამი 10-ის ტოლია
      განიხილე(A[a] * 10 + A[b], A[c] * 10 + A[d]);
      U[c] := false;
    end;
    U[b] := false;
  end;
  U[a] := false;
end;


გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.





პირველ რიგში შევინახოთ მხედრის შესაძლო სვლები გამოყენებისთვის მოხერხებული სახით. შეგვიძლია ეს გავაკეთოთ ორი dx და dy მასივის მეშვეობით ისე, რომ (dx[i], dy[i]) იყოს i-ური სვლის შესაბამისი გადაადგილების ვექტორი. მაგალითად, dx[1] = 1 და dy[1] = -2. ეს მასივები პროგრამაში ხელით უნდა გავწეროთ. მათი გამოყენებით მარტივია (x, y) უჯრიდან i-ური სვლით მიღებული ახალი პოზიციის გამოთვლა: ეს იქნება უჯრა (x + dx[i], y + dy[i]).

უშუალოდ მიღწევადი უჯრები შეგვიძლია სიმულაციით ვიპოვოთ. მოვახდინოთ გარკვეული რაოდენობის იტერაცია. ყოველ იტერაციაზე განვიხილოთ დაფის ყველა მიღწევადი უჯრა და მისი მეზობლებიც მიღწევადებად მოვნიშნოთ. ცხადია, თუ იტერაციები საკმარისი იქნება, ასე ყველა მიღწევად უჯრას მოვნიშნავთ. ფსევდოკოდში ეს მიდგომა ასე გამოიყურება:

For it = 1 to total_it do
  For i = 1 to N do
    For j = 1 to N do
      If მიღწევადია[i][j] then
        For d = 1 to M do
          If დაფაზეა(i + dx[სვლა[d]], j + dy[სვლა[d]]) then
            მიღწევადია[i + dx[სვლა[d]]][j + dy[სვლა[d]]] := true;

როგორ შევარჩიოთ იტერაციების რაოდენობა? შეგვიძლია ასეთი უხეში მიახლოებით ვიხელმძღვანელოთ: მხედრის სვლებით უჯრიდან მის ჰორიზონტალურად ან ვერტიკალურად მეზობელ უჯრაში გადასვლა 3 სვლაში ხდება, ანუ დაფის ერთი კუთხიდან მეორეში 3 * 2 * N სვლაზე მეტი ნამდვილად არ დამჭირდება, სხვა უჯრედებში ხომ სულაც ნაკლები. ამიტომ 6*N იტერაცია ნამდვილად საკმარისია და ამ სიმულაციური ალგორითმის სირთულე O(N3 * M) არის. სავარჯიშოს სახით შეგიძლიათ იტერაციულის მაქსიმალური რაოდენობის ზუსტი ზღვარი გამოთვალოთ.


გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.





გამოვიყენოთ დინამიური პროგრამირების პრინციპი. F(i, j) იყოს i ჯამური ღირებულების მქონე მარკათა მინიმალური რაოდენობა, თუ ვიყენებთ მხოლოდ მარკებს ნომრებით 1..j (ამ დროს ზოგი მათგანი შეიძლება არც გვქონდეს აღებული, მთავარია რომ არ ვიყენებთ k > j ნომრების მქონე მარკებს). დაგვჭირდება პირობითი უსასრულობის ცნება ისეთი F-ებისთვის, რომლებიც საერთოდ არ მიიღწევა - მაგალითად, F(i, 0), როცა i > 0, საერთოდ არ არსებობს.

გვაქვს საბაზო შემთხვევა F(0, j) = 0, ანუ 0 ჯამური ღირებულება 0 მარკით მიიღება ნებისმიერი j-სთვის.

როცა i > 0 და j > 0, გვაქვს F(i, j) = MIN(F(i, j – 1) + F(i – P[j], j)), სადაც P[j] არის j-ური მარკის საფასური (თუ P[j] > i, გვაქვს პირდაპირ F(i, j) = F(i, j – 1)). განვმარტოთ ეს ფორმულა: F(i, j)-ს მისაღებად შეიძლება აგვეღო j-ური მარკა, რაც ნიშნავს რომ (i – P[j]) ღირებულების მქონე მინიმალური მარკების რაოდენობა გვაინტერესებს. დავაზუსტოთ, რომ j-ური მარკა შეიძლება ერთზე მეტჯერაც გამოვიყენოთ, ამიტომ F(i – P[j], j)-ს ვაკითხავთ და არა F(i – P[j], j – 1)-ს - რა შემთხვევაშიც გამოვთვლიდით, არაუმეტეს 1-ხელ რომ ავიღოთ კონკრეტული მარკა, რა მინიმალური რაოდენობაა საჭირო. შეიძლება j-ური მარკა არც აგვეღო - მაშინ გვაინტერესებს მაგ მარკის გარეშე მინიმუმ რამდენი მარკა იყო საჭირო i-ს მისაღებად, ანუ F(i, j – 1).

ვინაიდან 0 ≤ i ≤ S, ხოლო 1 ≤ j ≤ N, ამ ფორმულაზე დაფუძნებული ალგორითმი O(S * N) დროში იმუშავებს. როგორც ხედავთ, აღწერილი მეთოდი არ ეფუძნება იმას, რომ მარკების საფასურები განსხვავებულია. არსებობს უფრო მარტივი ალგორითმი (თუმცა უფრო ნელიც), რომელიც ამ გარემოებასაც ითვალისწინებს.


გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.