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

პირველი დივიზონის მონაწილეებისთვის
მეორე დივიზონის მონაწილეებისთვის

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

11:00-zea xo mgoni?

კი.

H ამოცანა დროში მეჭრება 35-ე ტესტზე ( n=2*10^9 k=1 )
როგორია ოპტიმალური ამოხსნა k=1 -ისთვის?
ჩემი პროგრამა O(n)-ში მუშაობს k=1 ისთვის და O(sqrt(n))-ში k>1 ისთვის..

2 მილიარდია N და რა ხეირი O(N)-ისგან? :)

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

ასეთი რაოდენობა რამდენი განსხვავებული სიგრძის შუალედს შეესაბამება, ალბათ მარტივად შეიძლება იპოვო (მე დამეზარა და ორობითი ძებნა დავწერე, ანუ მთლად sqrt(N) დრო არ მაქვს).

ამის პოვნა როგორ შეიძლება? ისიც ხომ გვირთულებს საქმეს რომ თავდაპირველი ხის მარცხნივ და მარჯვნივ დასარგავი ხეების რაოდენობა არაა ფიქსირებული?

აი შეხედე. ვთქვათ იმ ერთადერთი ხისგან მარცხნივ L ცარიელი ადგილია, მარჯვნივ კი R. ავიღოთ Q = sqrt(N) + 1 და ვთქვათ L/Q = nL, ხოლო R/Q = nR (ანუ Q შუალედით რამდენი ხე ეტევა მარცხნივ და მარჯვნივ). ახლა ვნახოთ ისეთი მინიმალური X, რომ L/X < nL ან R/X < nR (ანუ ისეთი უმცირესი შუალედის სიგრძე, რომლისთვისაც nL და/ან nR ცალი აღარ ისმევა). ხომ გამოვა, რომ პასუხს უნდა დაემატოს (Q - X) * (nR + 1) * (nL + 1) - 1? (ანუ ყოველი შუალედი [X+1, Q]-დან გვაძლევს ზუსტად nL ხეს მარცხნივ და nR-ს მარჯვნივ, +1 იმიტომაა რომ შემიძლია სულ არ მქონდეს მარცხნივ/მარჯვნივ ხეები და -1 იმიტომ, რომ 1 ცალი ხე არ ჩავთვალო ბევრჯერ). ამის მერე Q გახდება X-ის ტოლი, nL ან nR ან ორივე შემცირდება და იგივეს გავიმეორებთ.

ეგ X დაახლოებით უნდა გამოვიდეს L/(nL-1) და R/(nR-1)-ს შორის მინიმალური, მაგრამ იქ კერძო შემთხვევებია როცა 0-ია ერთ-ერთი და ასე შემდეგ და ამიტომაც ორობითი ძებნა ვამჯობინე.

N - ამოცანაში პასუხი მაქსიმუმ რამდენნიშნა შეიძლება ყოფილიყო?

ვინ ამოხსნა რო? =)

ისე დავდებ აქ Upsolving-ის ბმულს:
Upsolving

პირობა დადეთ და ამოვხსნათ ერთობლივი ძალებით :)

N ამოცანის პირობა მართლა გაუგებარი იყო

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

ამოხსნა ალბათ ასეთია: გადაარჩიე რამდენნიშნაა X. ვთქვათ X არის n ნიშნა, B არის k-ნიშნა. მიიღებ განტოლებას
(B*10^n+X)*A=(X*10^k+B)
A*B*10^n-B = (10^k-A)*X;
X = (A*B*10^n-B) / (10^k-A).

აქ დიდი რიცხვების ოპერაციებია ჩასატარებელი. მგონი ჯერ უნდა შეამოწმო იყოფა თუ არა (ეს O(1) ში შეიძლება, რადგან გამყოფი პატარა რიცხვია). იმედია არაფერი არ შემეშალა. ცადეთ, მაინტერესებს რა არის სირთულე ამ ამოცანის.

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