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

#	ამოცანა	ავტორი
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-ის ალგორითმი.

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