მეხუთე ეპიზოდის გარჩევები

#	ამოცანა	ავტორი
A	card	დავით რაჭველიშვილი
B	credit	დავით რაჭველიშვილი
C	sqrt	დავით რაჭველიშვილი
D	tree	დავით რაჭველიშვილი
E	parts	დავით რაჭველიშვილი

ამოცანა A. "სადებეტო ბარათი"

ამოცანა არის ტრივიალური და მის ამოსახსნელად საჭიროა მხოლოდ დავითვალოთ ბარათის ნომერში არსებული 7იანების რაოდენობა და შევამოწმოთ გვხდება თუ არა ის ერთად აღებულ დანარჩენ ციფრებზე მეტჯერ ანუ 8ზე მეტჯერ.

ამოცანა B. "კრედიტი"

ამოცანის შეზღუდვებიდან გამომდინარე მის ამოსახსნელად საჭიროა მარტივი სიმულაცია. ყოველი თვისათვის საჭიროა დავთვალოთ რა პროცენტი დაერიცხება ნემოს და გადახდის შემდეგ რამდენი დარჩება მას ბანკის ვალი. ამ მარტივი მოდელირებისათვის იხილეთ კოდი:
cin >> M >> K >> N >> T;
for(int i = 0; i < T && M > 0; i++){
  M = M + K * M/100.0 - N;
}
if(M < 0) M = 0.0;
printf("%.2lf\n", M);

ამოცანა C. "ფესვის ამოღება"

პირველი და უმარტივესი ამოხსნა რაც მოგვდის თავში ამ ამოცანის წაკითხვისას არის ციკლი 1დან Nმდე რომელიც თანმიმდევრულად დაითვლის floor( sqrt(i) ) მნიშვნელობებს და აჯამავს.მაგრამ 1 <= N <= 1000000000000 (10^12) ამიტომ ეს ამოხსნა არ იმუშავებს და საჭიროა ეფექტური ალგორითმის მოფიქრება.
დავაკვირდეთ ფუნქცია floor( sqrt(x) ) მნიშვნელობებს საიდანაც ადვილად დავინახავთ ეფექტურ ალგორითმს.

x	1	2	3	4	5	6	7	8	9	10	11	12	13
floor( sqrt(x) )	1	1	1	2	2	2	2	2	3	3	3	3	3

 
 

x	14	15	16	17	18	19	20	21	22	23	24	25	26
floor( sqrt(x) )	3	3	4	4	4	4	4	4	4	4	4	5	5

მოცემული მნიშვნელობებიდან ვხედავთ რომ ფუნქციის მნიშვნელობა იცვლება მხოლოდ სრულ კვადრატებზე და ტოლი რიცხვების რაოდენობა კენტი რიცხვების მიმდევრობაა. აქედან გამომდინარე შეგვიძლია იტერაცია მოვახდინოთ ფუნქციის მნიშვნელობებზე ანუ sqrt(N)-მდე და ავჯამოთ მატი რაოდენობები. ამ ალგორითმის სირთულე წარმოადგენს O(sqrt(N)) რაც მისაღებია.

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

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

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

ამოცანა E. "დეტალები"

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

ეხლა დავაკვირდეთ იმას თუ რას ნიშნავს პირველი ფიგურა შესაძლებელია ჩაისვას მეორე ფიგურაში კონკრეტულ ადგილზე. ადვილად დავინახავთ, რომ ამისათ[ის აუცილებელი და საკმარისი შესაბამისი სამკუთხედები იყვნენ ტოლი. ანუ ამოცანის ამოსახსნელად საჭიროა დავთვალოთ პირველი სამკუთხედების მიმდევრობა რამდენჯერ გვხვდება მეორე მიმდევრობაში ანუ თუ სამკუთხედს განვიხილავთ როგორც ერთ რაიმე სიმბოლოდ, მაშინ ამოცანა დადის ქვესტრიქონის ძებნაზე. ხოლო ქვესტრიქონის რაოდენობების მოსაძებნად შეგვიძლია გამოვიყენოთ Knuth–Morris–Pratt-ის ალგორითმი.

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

მოგესალმებით,

ორიოდე დღის წინ საქართველოს ნაკრები გაემგზავრა კანადაში ინფორმატიკის საერთაშორისო ოლიმპიადაზე. ნაკრები შედგება 4 მონაწილისგან:

1) მარიამ კობიაშვილი

2) ნოდარ ამბროლაძე

3) ცოტნე ტაბიძე

4) ნიკა ბეგიაშვილი

ოლიმპიადა ტარდება ორ დღედ 16 და 18 აგვისტოს. წელს ოლიმპიადის ჩატარების წესები ოდნავ შეიცვალა და მიმდინარე შედეგების თვალყურის დევნება შესაძლებელია ონლაინ რეჟიმში შემდეგ მისამართზე: http://www.ioi2010.org/results.shtml

ოლიმპიადაზე სრული ინფორმაციის მოპოვება შეგიძლიათ მისი ოფიციალური საიტიდან.

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

ჯეოლიმპი უსურვებს ნაკრებს წარმატებას gl & hf ;)

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

საერთო ჩათვლაში გამარჯვებულები არიან:

1. ნოდარ ამბროლაძე (Sch #41)

2. ცოტნე ტაბიძე (Sch #41)

3. მარიამ კობიაშვილი (Sch Demireli College)

მოსწავლეებს შორის:

1. ნოდარ ამბროლაძე (Sch #41)

2. ცოტნე ტაბიძე (Sch #41)

3. მარიამ კობიაშვილი (Sch Demireli College)

სტუდენტებს შორის:

1. ლევან ვარამაშვილი (Tbilisi SU)

2. აკაკი მამაგეიშვილი (Tbilisi SU)

3. ელენე ლაცოშვილი (Tbilisi SU)

ტექნიკური პრობლემების გამო შეჯიბრების დაწყების დრო გადაიწია 10 წუთით, ანუ დაიწყება 11:10-ზე.

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

შეგიძლიათ გადმოწეროთ ამოცანების არქივი.

შედეგების ლაივში ყურება შეგიძლიათ შემდეგ მისამართზე

გისურვებთ ყველას წარმატებას.

2010 წლის 25 ივლისს 12 საათზე ჩატარდება შეჯიბრებათა ციკლის V ეპიზოდი.

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

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