წრიული ლაბირინთი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: GEOI, 2010, რეგიონული, XI-XII კლასები


ანდრო იდაძე მოხვდა ლაბირინთში, რომლის კედლები N (1≤N≤100,000) ცალი განსხვავებული ღი (1≤Ri≤1,000,000) რადიუსის მქონე კონცენტრული წრისაგან არის აგებული. კონცენტრული წრეები გადანომრილია ცენტრიდან დაშორების მიხედვით და ყოველ მათგანს აქვს Ki (1≤Ki≤6) კარი, რომელიც ძნელი შესამჩნევია, ამიტომ ანდრომ გადაწყვიტა, ყოველ კარში გასვლის შემდეგ მომდევნო კედლამდე იმოძრაოს ამ კარისა და წრეების საერთო ცენტრის შემაერთებელი რადიუსის გასწვრივ მომდევნო კედლამდე. შემდეგ კი გააგრძელოს მოძრაობა ახალი წრიული კედლის გასწვრივ მარჯვნივ ან მარცხნივ, ვიდრე კარს არ მოძებნის და ა.შ.   

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

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

 

შესატანი მონაცემები:

პირველ სტრიქონში: ერთი მთელი რიცხვი N - წრეების რაოდენობა. მომდევნო N სტრიქონიდან თითოეულში: მოცემული ჰარით გაყოფილი მთელი რიცხვები შემდეგი თანმიმდევრობით: წრის რადიუსი - Ri, შესაბამის წრეზე კართა რაოდენობა - Ki, კართა შესაბამისი გრადუსები, რომლებიც წარმოადგენენ მთელ რიცხვებს 0-დან 360-მდე ჩათვლით. წრეები შემომავალ ფაილში რადიუსის ზრდის მიხედვითაა დალაგებული.

გამოსატანი მონაცემები:

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




მაგალითები

შესატანი მონაცემები
3 4 2 60 263 6 2 188 320 9 3 30 135 246 დაკოპირება
გამოსატანი მონაცემები
32 დაკოპირება

შენიშვნა