#Problem Name

Time Limit

Memory Limit

Astandings

1 sec.

64 MB

Blab

1 sec.

64 MB

Ccompute

2 sec.

64 MB

Dboardwalk

2 sec.

64 MB

E

tournament

2 sec.

64 MB

Ftriangle

1 sec.

64 MBGgeolymp

1 sec.

64 MB

H

harmful

1 sec.

64 MB

I

permutation

1 sec.

64 MBამოცანა A. "შედეგები"ჯეოლიმპის ყოველი რაუნდის შემდეგ ჩვენ გვიწევს სისტემის მიერ დაგენერირებულისაბოლოო

შედეგებისორად

გაყოფა,რათაშემოგთავაზოთ

მოსწავლეებისდასტუდენტების შედეგები ცალ-ცალკე. ზუსტად ამ ფუნქციის ავტომატიზაცია იქნებათქვენი დავალება.

შეზღუდვები:შემომავალი კონტესტის შედეგი შედგება 1 <= N <= 100 სტრიქონისაგან.

შემომავალი ფაილის ფორმატი:standings.in ფაილის პირველ სტრიქონში მოცემულია N, მონაწილეთა რაოდენობა.
შემდეგ N სტრიქონში მოცემულია სისტემის მიერ დაგენერირებული კონტესტისშედეგები.
თითოეულ სტრიქონში მოცემულია თითო ჰარით გამოყოფილი მონაწილის პოზიცია,სახელი, გვარი და ფრჩხილებში ჩაწერილი სასწავლო დაწესებულება.
მონაწილის პოზიცია განისაზღვრება ერთი რიცხვით ან ტირით გამოყოფილი ორირიცხვით და ბოლოვდება წერტილით. თუ მონაწილის პოზიციაა 3-7, ეს ნიშნავს რომ 5მა მონაწილემ აჩვენა ერთიდაიგივე შედეგი და შესაბამისად დაიკავეს მე-3 დან მე-7-ს
ჩათვლით ადგილები. მონაწილეები დალაგებულები იქნებიან პოზიციის მიხედვით დაპოზიციები სწორად იქნება მითითებული.
მონაწილის სახელი და გვარი წარმოადგენენ არაცარიელ დიდი და პატარა ლათინური
ასოებისგან შემდგარ სიტყვებს.
სასწავლო

დაწესებულებაარის

ორიტიპის:

უმაღლესიდა

სკოლა.

სკოლის

შემთხვევაში სასწავლო დაწესებულების დასახელება იწყება ‘Sch’ სიტყვით (ასოებისრეგისტრი არსებითია, ანუ “SCH” სკოლის მოსწავლეს არ განსაზღვრავს). სასწავლოდაწესებულების სახელში სიტყვები ერთმანეთისაგან გამოყოფილია ერთი ჰარით.
ყოველისიტყვაშედგებაშედგებადიდიდა

პატარა

ციფრებისასგან და ’,’ , ’.’ , ’#’ სიმბოლოებისაგან.
თითოეული სტრიქონის სიგრძე არ აღემატება 100 სიმბოლოს.

ლათინურიასოებისაგან,გამომავალი ფაილის ფორმატი:standings.out ფაილში დაბეჭდეთ ჯერ სტუდენტების შედეგები, შემდეგ ცარიელი ხაზიდა შემდეგ მოსწავლეების შედეგები იგივე ფორმატით როგორც შემომავალ ფაილშია.
საჭიროების შემთხვევაში, მოახდინეთ პოზიციების გადანომვრა. თუ რამოდენიმემონაწილეს ერთიდაიგივე შედეგი აქვს, დაბეჭდეთ ისინი იმავე თანმიმდევრობითროგორც შემომავალ ფაილშია მოცემული.
შემომავალი ფაილის მაგალითი (standings.in)გამომავალი ფაილის მაგალითი(standings.out)

8
1. Irakli Merabishvili (Spb SU)
2. Levan Varamashvili (Tbilisi SU)
3-5. Akaki Mamageishvili (Tbilisi SU)
3-5. Giorgi Nadiradze (Tbilisi SU)
3-5. Nodar Ambroladze (Sch #41)
6. Nika Gabisonia (Tbilisi SU)
7. Emzar Ulvashidze (Tbilisi SU)
8. Tsotne Tabidze (Sch #41)

1. Irakli Merabishvili (Spb SU)
2. Levan Varamashvili (Tbilisi SU)
3-4. Akaki Mamageishvili (Tbilisi SU)
3-4. Giorgi Nadiradze (Tbilisi SU)
5. Nika Gabisonia (Tbilisi SU)
6. Emzar Ulvashidze (Tbilisi SU)
1. Nodar Ambroladze (Sch #41)
2. Tsotne Tabidze (Sch #41)

ამოცანა B. "ლაბორატორია"ერთ-ერთ ლაბორატორიაში იკვლევენ წყლის შემადგენლობას, რისთვისაც მეცნიერები
იყენებენ N რაოდენობის წყლით სავსე ცილინდრს. ცილინდრების M რაოდენობისწყვილი შეერთებულია ერთმანეთთან მილით, რაც უზრუნველყოფს მათ შორის წყლის
ცირკულაციას. ყოველი ცდის შემდეგ ცილინდრებიდან არათანაბრად ორთქლდებაწყალი, ხოლო მომდევნო ცდის ჩატარებამდე აუცილებელია მათში წყლის სიმაღლეებისგათანაბრება.
ყველა ცილინდრის ფუძის დიამეტრი ტოლია. ასევე მათ მთელ სიმაღლეზე მიჰყვებათშკალა, რომლის საშუალებითაც შეიძლება განისაზღვროს თუ რა სიმაღლემდე ასხიამათში წყალი.
სამწუხაროდ, ცილინდრიდან წყლის გადასხმა შეუძლებელია, ხოლო მასში წყლისდონისერთიერთეულითასამაღლებლადსაჭიროაელექტროენერგია.

საჭიროენერგიის მოცულობა დამოკიდებულია იმაზე, თუ რამდენ სხვა ცილინდრთან არისშეერთებული მოცემული ცილინდრი და ჯამში რა რაოდენობის წყალი ასხია მისმოსაზღვრე ცილინდრებში. კონკრეტულად, თუ A არის X ცილინდრის მოსაზღვრეცილინდრებშიწყლისსიმაღლეებისჯამისხოლოBმოსაღზვრე

ცილინდრებისრაოდენობა, X ცილინდრში წყლის დონის 1 ერთეულით ასაწევად საჭიროაერთეულიელექტროენერგია.
მოცემული გაქვთ ცილინდრებში წყლის სიმაღლეები ცდის შემდეგ დაინფორმაცია

მილებით შეერთებულ წყვილებზე. თქვენი ამოცანაა დაადგინოთ ელექტროენერგიისსაჭირო მინიმალური რაოდენობა, რომლის გამოყენებითაც შესაძლებელია ცილინდრებშიწყლის სიმაღლეების გათანაბრება.

შეზღუდვები:2 <= N <= 50
1 <= M <= 250
ყოველ ცილინდრში წყლის დონე მთელი რიცხვია [0, 100] შუალედიდან.
ასევე გარანტირებულია, რომ წყალს ნებისმიერი ცილინდრიდან სხვა ნებისმიერ
ცილინდრში შეუძლია მოხვედრა ცირკულაციის შედეგად.

შემომავალი ფაილის ფორმატი:lab.in ფაილის პირველ სტრიქონში წერია ორი მთელიN და M რიცხვი. მომდევნოსტრიქონში მოცემულია ზუსტად N ნატურალური რიცხვი, რომელთაგან i-ური აღნიშნავსi-ურ ცილინდრში წყლის საწყის დონეს. მომდევნო M სტრიქონიდან თითოეულიშეიცავს ორ ნატურალურ i და j რიცხვს, რაც აღნიშნავს რომ i-ური და j-ური ცილინდრებიშეერთებულები არიან მილით.

გამომავალი ფაილის ფორმატი:lab.out ფაილში დაბეჭდეთ წყლის დონეების გათანაბრებისთვის საჭირო მინიმალურიენერგია. თქვენი პასუხი სწორისგან არ უნდა განსხვავდებოდეს 0.01-ზე მეტით.
შემომავალი ფაილის მაგალითი(lab.in)გამომავალი ფაილის მაგალითი(lab.out)

431321
1223
24

15.00

ამოცანა C. "გამოთვლა"მოცემულია მიმდევრობა A = {A1,A2,...,AN}. ყოველი i-სთვის 1-დან N-ის ჩათვლით,გამოთვალეთ Si = A1 * ... * Ai-1 * Ai+1 * ... * AN. შემდეგ დაითვალეთ S = S1 + S2 +...+ SNდა გამოიტანეთ S-ის 1,000,000,009-ზე გაყოფისგან ნაშთი.

შეზღუდვები:2 <= N <= 100,000მიმდევრობის ყოველი წევრის მნიშვნელობა არის [1, 1000000008] შუალედში.

შემომავალი ფაილის ფორმატი:compute.in ფაილის პირველი სტრიქონი შეიცავს ერთ მთელ რიცხვს N. შემდეგმოცემულია N რიცხვი, რომლებიც A მიმდევრობის წევრებს წარმოადგენენ.

გამომავალი ფაილის ფორმატი:compute.out ფაილში გამოიტანეთ S-ის ნაშთი 1000000009-ზე გაყოფისგან.
შემომავალი ფაილის მაგალითი (compute.in)გამომავალი ფაილის მაგალითი (compute.out)

32 4 538განმარტება.
S1 = A2*A3 = 4*5 = 20
S2 = A1*A3 = 2*5 = 10
S3 = A1*A2 = 2*4 = 8
S = S1 + S2 + S3 = 38ნაშთი S-ის 1000000009-ზე გაყოფისგან 38-ის ტოლია.

ამოცანა D. "გასეირნება"მოცემულია

NxMუჯრედისგანშემდგარი

დაფა.

მისზედა

მარცხენა

კუთხეში

კოორდინატებით (1,1) დგას მანაო და უნდა ქვედა მარჯვენა (N,M) უჯრედში მოხვედრა.
წერტილიდან მას მხოლოდ ქვევით ან მარჯვნივ შეუძლია მეზობელ უჯრედშიგადასვლა, ანუ უჯრედიდან კოორდინატებით (i,j) იგი შეიძლება უჯრედებში (i+1,j) ან(i,j+1) გადავიდეს.
დაფაზე მონიშნულია K წერტილი, რომლებზეც მანაომ აუცილებლად უნდა გაიაროს.
დაითვალეთ, რამდენნაირად შეუძლია მას თავისი გზის გავლა. ვინაიდან ეს რიცხვიშეიძლება ძალიან დიდი იყოს, გამოიტანეთ მისი ნაშთი 1,000,000,009-ზე გაყოფისას.

შეზღუდვები:2 <= N, M <= 100,000
0 <= K <= 100,000
K აუცილებლად მოსანახულებელი უჯრედის კოორდინატები [1..N], [1..M] შუალედებშიამოთავსებული.

შემომავალი ფაილის ფორმატი:boardwalk.in ფაილის პირველი სტრიქონი შეიცავს სამ მთელ რიცხვს N, M და K.
მომდევნო K სტრიქონი შეიცავს თითოეული მონიშნული უჯრედის კოორდინატებს.

გამომავალი ფაილის ფორმატი:boardwalk.out ფაილის ერთადერთ სტრიქონზე დაბეჭდეთ განხსვავებული გზების
რაოდენობის ნაშთი 1000000009 გაყოფისგან.
შემომავალი ფაილის მაგალითი (boardwalk.in)გამომავალი ფაილის მაგალითი(boardwalk.out)

22 2
3 418განმარტება.
იხილეთ მანაოს ერთ-ერთი შესაძლო მარშრუტი.

ამოცანა E. "ჩემპიონატი"ჭ-ბურთის ჩემპიონატში N გუნდი იღებს მონაწილეობას. თითოეულ გუნდს თავისი
მოედანი აქვს, რომელზეც მას ჩემპიონატის განმავლობაში ყველა სხვა გუნდთანმოუწევს თითო თამაშის ჩატარება. ანუ ჯამში ჩემპიონატი N*(N-1) თამაშს მოიცავს.
მატჩიყოველთვისერთ-ერთიგუნდისგამარჯვებითსრულდებადაამისთვისგამარჯვებული 1 ქულას იღებს.
ჩემპიონატის დასრულებისას 2 ცხრილს ადგენენ: Tournament Table და Rankings.
Tournament Table წარმოადგენს NxN ზომის მატრიცას, რომლის (i, j) ელემენტები(განსხვავებული i და j-სთვის) შეიცავენ i-ურ და j-ურ გუნდებს შორის i-ური გუნდისმოედანზე ჩატარებული მატჩის შედეგს.
Rankings წარმოადგენს ცხრილს, რომელშიც ჩემპიონატში მონაწილე ყველა გუნდიდალაგებულია დაგროვებული ქულების მიხედვით.
მაგალითად, განვიხილოთ შემდეგი Tournament Table:
1
12

3

4

WinLose

Lose

Lose

Win2

Win

3Win

Lose

4Lose

Lose

WinLoseცხრილი გვიჩვენებს, რომ გუნდმა №1 თავის მოედანზე მოუგო №2-ს და წააგომესამესთან და მეოთხესთან. მეორე გუნდმა სახლში დაამარცხა გუნდები 1 და 4 დაწააგო მესამესთან. მესამე გუნდმა თავის მოედანზე წააგო მეორესთან და მოუგო №1 და№4-ს. მეოთხე გუნდმა სახლში ყველა მატჩი წააგო.
შესაბამისად, ამ ჩემპიონატის Rankings ცხრილს შემდეგი სახე ექნება:TeamScore

Team35Team24Team12Team41თუ ქულათა სხვაობა ჩემპიონატის ლიდერს და ბოლოადგილოსანს შორის აღემატებაK-ს, მაშინ Rankings-ს მეჩხერს ეძახიან. დაითვალეთ, რამდენი ისეთი Tournament Tableარსებობს, რომელსაც მეჩხერი Rankings ცხრილი შეესაბამება.
შეზღუდვები:2 <= N <= 60 <= K <= 9შემომავალი ფაილის ფორმატი:tournament.in ფაილის ერთადერთი სტრიქონი შეიცავს რიცხვებს N და K.
გამომავალი ფაილის ფორმატი:tournament.out ფაილში გამოიტანეთ ამოცანის პასუხი.
შემომავალი ფაილის მაგალითი(tournament.in)გამომავალი ფაილის მაგალითი(tournament.out)

2 023 218განმარტება.
პირველ მაგალითში შემდეგ ორ Tournament Table-ს შეესაბამება მეჩხერი Rankings:
LoseWinWinLoseამოცანა F. "სამკუთხედი"განვიხილოთ მართკუთხა სამკუთხედი. თვალსაჩინოა, რომ მართი კუთხის წვეროდანჰიპოთენუზაზესიმაღლესთუდავუშვებთ,ესსამკუთხედიორმართკუთხასამკუთხედად დაიყოფა.

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

საწყისი სამკუთხედის კათეთების სიგრძეები თუ არის A და B, და მოცემული ოპერაციაK-ჯერ შევასრულეთ, რა იქნება დარჩენილი სამკუთხედის მაქსიმალური შესაძლოფართობი?

შეზღუდვები:1 <= A, B <= 100A და B მთელი რიცხვებია.
1 <= K <= 10შემომავალი ფაილის ფორმატი:triangle.in ფაილის ერთადერთი სტრიქონი შეიცავს სამ მთელ რიცხვს A, B და K.

გამომავალი ფაილის ფორმატი:triangle.out ფაილში გამოიტანეთ შემორჩენილი სამკუთხედის მაქსიმალური შესაძლოფართობი. თქვენი პასუხი სწორისგან 1e-5-ზე მეტით არ უნდა განსხვავდებოდეს.
შემომავალი ფაილის მაგალითი (triangle.in)გამომავალი ფაილის მაგალითი (triangle.out)

3 4 1

3.84

6 8 3

6.291456

განმარტება.
იხილეთ მეორე მაგალითის შესაბამისი ყველა შესაძლო დარჩენილი სამკუთხედი.
მაქსიმალური ფართობის მქონე სამკუთხედი ყვითლად არის შეღებილი:ამოცანა G. "GEOLYMP"

სტრიქონ S-ის ქვემიმევრობა ეწოდება ისეთ სტრიქონს, რომელიც მიიღება S-იდან 0ან მეტი სიმბოლოს ამოშლით. მაგ. ABC, AA და AD წარმოადგენენ სტრიქონ ABCDA-სქვემიმდევრობებს, ხოლო ACB და XYZ არა.
ჩვენ გვაინტერესებს სტრიქონები, რომლებიც ქვემიმდევრობად სიტყვა GEOLYMP-სშეიცავენ. კერძოდ, მოცემული K-სთვის უნდა იპოვოთ რომელიმე სტრიქონი, რომლისსიგრძე არ აღემატება 1000 სიმბოლოს და რომლის ზუსტად K ქვემიმდევრობა ტოლიაGEOLYMP-ის.

შეზღუდვები:1 <= K <= 1,000,000,000შემომავალი ფაილის ფორმატი:geolymp.in ფაილის ერთადერთი სტრიქონი შეიცავს ერთ მთელ რიცხვს K.

გამომავალი ფაილის ფორმატი:geolymp.out ფაილში გამოიტანეთ არაუმეტეს 1000 ზედა რეგისტრის ლათინურიასოსგან შემდგარი სტრიქონი, რომლის ზუსტად K ქვემიმდევრობა არის GEOLYMP.
შემომავალი ფაილის მაგალითი (geolymp.in)გამომავალი ფაილის მაგალითი (geolymp.out)

5

GXEOLYMPMPPგანმარტება.
მოცემული ტესტისთვის სწორი პასუხი ასევე იქნება GABCDEOLYMPPPPP,GEOLYMPPPMP და მრავალი სხვა.

ამოცანა H. "მავნე სუბიექტები"მარიმ NxM უჯრედისგან შემდგარ დაფაზე დახატა ძალიან ლამაზი ფიგურა. კერძოდ,მან ზოგი უჯრედი შავად შეღება, ზოგი კი თეთრი დატოვა. ორ უჯრედს მეზობლებიდავარქვათ, თუ მათ საერთო გვერდი გააჩნიათ. უჯრედების წყვილისთვის ვიტყვით,რომ ისინი ერთ ფიგურას ეკუთვნიან, თუ არსებობს უჯრედების ისეთი მიმდევრობა
A1, A2, ..., AK, სადაც A1 პირველი უჯრედია, AK - მეორე და ყოველი i-ისთვის 2-დან K–სჩათვლით Ai და Ai-1 უჯრედები მეზობლები არიან.
ამ დროს მოვიდნენ მავნე სუბიექტები სახელად ჟორა და მანაო. მათ გადაწყვიტესდაფაზე დახატული ფიგურის გაფუჭება მისი 1 ან 2 შავი უჯრედის გათეთრებით.
გაფუჭებად ისინი მოიაზრებენ ფიგურის დაშლას ორ ან მეტ ფიგურად, ანუ მათ მიერუჯრედების გათეთრების შემდეგ დაფაზე 1–ზე მეტი ფიგურა უნდა აღმოჩნდეს.
უჯრედების გათეთრების ორი გეგმა ითვლება განსხვავებულად, თუ არსებობს ისეთიუჯრედი, რომელიც ერთი გეგმის შესრულების შემდეგ შავი რჩება, ხოლო მეორე გეგმისშესრულებისას თეთრდება. დაითვალეთ მავნე გეგმების საერთო რაოდენობა.

შეზღუდვები:1 <= N, M <= 50დაფაზე 2 მაინც შავი უჯრედი იქნება.
თავდაპირველად დაფაზე 1 ფიგურა ხატია, ანუ შავი უჯრედების ნებისმიერი წყვილიერთ ფიგურას ეკუთვნის.

შემომავალი ფაილის ფორმატი:harmful.in ფაილის პირველი სტრიქონი შეიცავს ორ რიცხვს N და M. შემდეგ არის N ხაზი,თითოეულ რომელთაგანზე M სიმბოლოა მოთავსებული – დაფის აღწერა. აქედან iური სტრიქონის j-ური სიმბოლო შეესაბამება დაფის (i, j) უჯრედს და იქნება ‘.’, თუ ესუჯრედი მარიმ შავად შეღება, ან ‘X’, თუ თეთრად დატოვა.

გამომავალი ფაილის ფორმატი:harmful.out ფაილში გამოიტანეთ მავნე გეგმების რაოდენობა.

შემომავალი ფაილის მაგალითი (harmful.in)გამომავალი ფაილის მაგალითი (harmful.out)

3 4X.XX....
X.XX10განმარტება.
იხილეთ 10–ივე მავნე გეგმა:
X.XX
.X..
X.XX

X.XX
..X.
X.XX

X.XX.XX.
X.XX

X.XX.X.X
X.XX

XXXX
.X..
X.XX

X.XX
XX..
X.XX

X.XX
.X..
XXXX

X.XX
X.X.
X.XX

XXXX
..X.
X.XX

X.XX
..X.
XXXX

ამოცანა I. "გადანაცვლება"ალბათ გაგიხარდებათ, როდესაც გაიგებთ რომ ამ ამოცანას არანაირი ზღაპარი არა აქვსდა პირდაპირ გთხოვთ რომ მოცემული N-სთვის დაბეჭდოთ 1-დან N-მდე რიცხვებისისეთი გადანაცვლება, რომ მის მეზობელ ელემენტებს შორის სხვაობის მინიმუმი იყოსმაქსიმალური შესაძლო 1..N რიცხვების ყველა გადანაცვლებას შორის.

შეზღუდვები:2 <= N <= 100შემომავალი ფაილის ფორმატი:permutation.in ფაილის ერთადერთი სტრიქონი შეიცავს N-ს.

გამომავალი ფაილის ფორმატი:permutation.out ფაილის პირველ სტრიქონზე გამოიტანეთ ისეთი მაქსიმალური შესაძლოK, რომლისთვისაც არსებობს 1..N რიცხვების გადანაცვლება, რომელშიც არც ერთმეზობელ ელემენტთა წყვილში სხვაობა K-ზე ნაკლები არაა.
მეორე სტრიქონზე კი გამოიტანეთ შესაბამისი გადანაცვლება. თუ ასეთი გადანაცვლებარამდენიმეა, გამოიტანეთ ნებისმიერი.
შემომავალი ფაილის მაგალითი(permutation.in)გამომავალი ფაილის მაგალითი(permutation.in)

42
3 1 4 2