ამ ამოცანაში საკმარისია დავინახოთ, რომ არსებობს 3 შემთხვევა:

1. რეიტინგი r უარყოფითია. მაშინ გვჭირდება r უარყოფითი შეფასება, ანუ პასუხი იქნება -r.
2. რეიტინგი r დადებითი და ლუწია. მაშინ ასეთი რეიტინგის მიღება შეგვიძლია მარტო დადებითი შეფასებებით. ამ შემთხვევაში პასუხი იქნება r/2.
3. რეიტინგი r დადებითი და კენტია. მარტო ამ შემთხვევაშია საჭირო როგორც დადებითი ასევე უარყოფითი შეფასება. ჯერ უნდა მივაღწიოთ რეიტინგს r+1, რასაც (r+1)/2 შეფასება ჭირდება, ამის მერე კი ერთი უარყოფითი შეფასება მოგვცემს სასურველ შედეგს. საბოლოოდ პასუხია (r+1)/2+1.

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

გარჩევა მომზადებულია ანდრეი ლუცენკოს მიერ.

გავშალოთ ის ჯამი, რომელიც საბოლოოდ უნდა იყოს ans ცვლადში ციკლის შესრულების მერე. სიმარტივისთვის დავუშვათ, რომ ციკლი მიდის არა 1-დან N-მდე, არამედ 0-დან N-მდე. ეს პასუხს არ ცვლის, ასე რომ ჯამი ასე გამოიყურება

ans=(0+1+2+...+M-1) + (0+1+2+...+M-1) + (0+1+2+...+M-1)+ ... + (0+1+2+...+k)

შევნიშნოთ, რომ ბლოკი 0+1+2+...+M-1 ბლოკი მეორდება (N+1)/M-ჯერ (იგულისხმება მთელი გაყოფა), ხოლო ბოლო ბლოკი 0+1+2+...+k ავსებს ჯამის ელემენტების რაოდენობას N+1-მდე, ანუ შეიცავს (N+1)%M ელემენტს (იგულისხმება მთელი გაყოფისას ნაშთის აღება). რადგან ეს არითმეტიული პროგრესიებია, შეგვიძლია ეს ბლოკები სწრაფად დავითვალოთ ფორმულით.

საბოლოოდ გამოდის:

ans = (m*(m-1)/2) * ((n+1)/m) + ((n+1)%m) * ((n+1)%m-1)/2.

იმპლემენტაციის დროს არ უნდა დაგავიწყდეთ, რომ შემომავალი რიცხვები მილიარდამდეა, ასე რომ მათი ნამრავლი 4 ბაიტიან ტიპში ვერ ჩაეტევა. გადავსების ასარიდებლად უნდა გამოვიყენოთ 64 ბიტიანი მთელი რიცხვები (long long და int64).

გარჩევა მომზადებულია ანდრეი ლუცენკოს მიერ.

პირველ რიგში, ვიპოვოთ ყველაზე მაღალი ყუთების კოშკი საწყის მდგომარეობაში. აღვნიშნოთ მისი სიმაღლე H-ით. თუ რომელიმე სხვა კოშკი H-ზე ნაკლებ ყუთს შეიცავს, მაშინ ახალი ყუთები შეგვიძლია მასში ვამატოთ მანამ, სანამ კოშკის სიმაღლე H-მდე არ შეივსება. თუ S-ით აღვნიშნავთ ყველა კოშკის სიმაღლეების ჯამს, მაშინ ასეთი სტრატეგიით N*M*H-S ახალი ყუთის განლაგება შეგვიძლია. თუ K ამ რიცხვს არ აღემატება, მაშინ ამოცანის პასუხი H არის. წინააღმდეგ შემთხვევაში დაგვრჩება K-N*M*H+S ცალი ყუთი, რომლებიც უნდა განლაგდეს H სიმაღლის მქონე N*M ცალ კოშკზე. დამატება შეგვიძლია მოვახდინოთ შრეებად, ანუ დავადოთ ყველა კოშკს თითო ყუთი, შემდეგ ისევ ყველას კიდევ თითო ყუთი და ა.შ. მანამ, სანამ არ დაგვრჩება N*M-ზე ნაკლები რაოდენობის ყუთი. თუ ეს რაოდენობა 0-ზე მეტია, მაშინ რომელიღაც კოშკების სიმაღლეების კიდევ 1-ით გაზრდა მოგვიწევს. რა თქმა უნდა, რეალურად ეს ოპერაციები არ უნდა მოვახდინოთ. თუ დარჩენილია რაღაც რაოდენობა K' ყუთი, მაშინ ასეთი სრულად გავსებული შრეების რაოდენობა K' / (N*M) არის და კიდევ ერთიც დაგვჭირდება თუ K' არ იყოფა N*M-ზე.

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

განვიხილოთ ამ ამოცანის ამოხსნის ორი მიდგომა.

თავიდან ვცადოთ, ყოველი ნასროლი ხელშუბი დამოუკიდებლად განვიხილოთ. დავუშვათ, ხელშუბი მოხვდა წერტილში (X,Y). ჩვენ შეგვიძლია, განვიხილოთ ყოველი წრე და დავადგინოთ, შეიცავს თუ არა იგი მოცემულ წერტილს, რა შემთხვევაშიც ჯამური ქულა შესაბამისად გავზარდოთ. ამისთვის წერტილი სათავიდან არაუმეტეს R მანძილზე უნდა იყოს მოთავსებული, ანუ უნდა სრულდებოდეს პირობა X^2 + Y^2 ≤ R^2. ვინაიდან ყოველი ხელშუბისთვის K წრეს განვიხილავთ, ალგორითმის ჯამური სირთულე იქნება O(N*K), რაც დაწესებული შეზღუდვების პირობებში მიუღებელია.

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

ქულების ჯამები ხელშუბების განხილვამდე ერთხელ შეგვიძლია დავითვალოთ. ამისთვის შემოვიღოთ მასივი Q[], სადაც Q[i] იქნება i-ური წრიდან ყველაზე გარე წრემდე ქულების ჯამი. ამ აღნიშვნებში სწორი იქნება ფორმულა Q[i]=Q[i+1]+S[i], სადაც 0 ≤ i < K-1 და Q[K-1]=S[K-1]. ამ მნიშვნელობების გამოთვლა ყველაზე გარე წრიდან ყველაზე შიდასკენ ერთი გავლით შეიძლება.

საზოგადოდ, შემოთავაზებული დაჩქარება ზოგიერთ შემთხვევაში მოგებას არ იძლევა (მაგალითად, თუ ყველა ხელშუბი დაფის ყველაზე გარე შრეში მოხვდა). ვინაიდან ჩვენმა ალგორითმმა შეზღუდვების დამაკმაყოფილებელი ნებისმიერი მონაცემებისთვის უნდა იმუშავოს საკმარისად სწრაფად, ეს გაუმჯობესება ჯერ–ჯერობით უადგილოა. შევცვალოთ წრეების განხილვის მიმდევრობა: იმის ნაცვლად, რომ მივყვეთ მათ შიგნიდან გარეთ, პირველ ცდაზე განვიხილოთ შუა წრე. შუაში იგულისხმება ის, რომლის ინდექსი წრეების მიმდევრობაში შუა პოზიციაზე იმყოფება. თუ ეს წრე ჩვენს წერტილს შეიცავს, მაშინ ჩვენ ცალსახად გვეცოდინება, რომ მის გარეთაც ყველა წრე შეიცავს წერტილს და შეგვიძლია განხილვა წრეების შიდა ნახევარზე გავაგრძელოთ. წინააღმდეგ შემთხვევაში ამ წრეზე უფრო შიდა წრეები ვერ იქნებიან წერტილის შემცვლელები და შეგვიძლია განხილვა წრეების გარე ნახევარზე გავაგრძელოთ. მოვაცილებთ რა რომელიმე ნახევარს, იგივე პროცესი გავიმეოროთ. ასე გავაგრძელოთ მანამ, სანამ განსახილველი ინტერვალი არ შემცირდება რამდენიმე წრემდე, რომლებსაც შეგვიძლია უკვე პირდაპირი ციკლით მივყვეთ. კარგად გააზრების შედეგად შეიძლება ისეთი ძებნა დავწეროთ, რომელსაც ეს ბოლო ნაბიჯიც არ დასჭირდება. ვინაიდან ყოველი იტერაციაზე საძებნი ინტერვალი ნახევრდება, იტერაციების საერთო რაოდენობა იქნება ⌈log₂K⌉. ალგორითმის ჯამური სირთულე გამოვა O(N*log₂K+K), რაც საკმაოდ სწრაფად მუშაობს მოცემულ შეზღუდვებში.

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

ალტერნატიულად, შეიძლება ყველა ხელშუბი ერთად განვიხილოთ და მუშაობის დრო ამის ხარჯზე შევამციროთ. დავალაგოთ წერტილები მათი სათავიდან მანძილის ზრდადობის მიხედვით. ამ მიმდევრობის პირველი წერტილისთვის ვიპოვოთ ისეთი პირველი წრე, რომელიც მას შეიცავს. მეორე წერტილის განხილვისას ჩვენ უკვე აღარ გვჭირდება უფრო შიდა წრეების განხილვა, ვინაიდან ისინი არ შეიცავენ მასზე სათავესთან უფრო ახლო წერტილს. ამგვარად, შეგვიძლია წრეების განხილვა დავიწყოთ იმიდან, რომელზეც გავჩერდით წინა წერტილისთვის. ეს ლოგიკა ყოველი შემდეგი წერტილისთვისაც იმუშავებს, ამიტომ ყველა წერტილის განვილვის შედეგად ჩვენ მაქსიმუმ ერთხელ გავივლით წრეების მიმდევრობას. ზევით აღწერილი ქულების ჯამების დათვლით კი ჩვენ შევძლებთ წრის დადგენისას დასამატებელი ქულა უცებ გავიგოთ. ამ ალგორითმის სირთულე O(N*log₂N+K) გახლავთ, სადაც ძირითადი დრო წერტილების დალაგებას სჭირდება.

გაითვალისწინეთ, რომ ამოცანის მაქსიმალური პასუხი შეიძლება N*K*max(S) იყოს, ანუ 50,000*50,000*1,000, რაც 4–ბაიტიანი მთელი ტიპის მაქსიმალურ მნიშვნელობას ბევრად აღემატება. ამიტომ პასუხის შესანახად უნდა გამოიყენოთ 8–ბაიტიანი მთელი ტიპი. ასევე სიფრთხილეა საჭირო მანძილების შედარებებში: იმის ნაცვლად, რომ რეალური მანძილი ითვალოთ წერტილიდან სათავემდე, ჯობია გამოთვალოთ ამ მანძილის კვადრატი, რომ ყველა ოპერაცია მთელ რიცხვებში გაკეთდეს და სიზუსტესთან პრობლემები არ გაჩნდეს. აქაც 4–ბაიტიანი ტიპი ზოგ ადგილას არ იქნება საკმარისი.

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

დაშვებული სიტყვების რაოდენობა A^N–ის ტოლია, რაც უკიდურეს შემთხვევაში 4¹⁰⁰ არის და ამიტომ მათ სათითაოდ განხილვაზე უარი თავიდანვე უნდა ვთქვათ. ამის მაგივრად შევეცადოთ, დავყოთ შესაძლო სიტყვები ერთგვარ კლასებად. ერთ კლასში მოვათავსოთ ისეთი სიტყვები, რომლებიც ერთმანეთის ანაგრამებს წარმოადგენენ. როდის წარმოადგენს ორი სიტყვა ერთმანეთის ანაგრამას? პასუხი მარტივია: ამისთვის პირველ სიტყვაში 'A' ასოების რაოდენობა უნდა უტოლდებოდეს 'A' ასოების რაოდენობას მეორე სიტყვაში, ანალოგიურად 'B', 'C' და 'D' ასოებისთვის (რა თქმა უნდა, ეს ამ კონკრეტულ ამოცანას ეხება. საზოგადოდ, ტოლები უნდა იყონ ანბანის ყველა შესაძლო სიმბოლოს სიხშირეები). ამ დაკვირვებიდან უკვე შეგვიძლია მოვახდინოთ ანაგრამების კლასების რაოდენობის შეფასება. ვინაიდან 'A', 'B' და 'C' ასოების სიხშირის დაფიქსირებისას 'D' ასოების რაოდენობა ცალსახად განისაზღვრება (გავიხსენოთ, რომ სიტყვის სიგრძეც ფიქსირებულია), კლასების რაოდენობა N³–ის რიგისაა. მეტიც, რადგან ეს სიხშირეები ჯამში N-ს არ უნდა აღემატებოდეს, კლასების რაოდენობა მკაცრად ნაკლებია N³-ზე. ამის გაანალიზების შემდეგ უკვე შეიძლება, ყველა შესაძლო კლასი სათითაოდ განვიხილოთ. რეალურად მათი რაოდენობა 176,851 გამოვა N=100, A=4 შემთხვევაში.

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

rec(სიმბოლოს_ინდექსი : integer
    დარჩენილი_სიგრძე : integer
    სიხშირეები       : integer{}
 )
begin
  if სიმბოლოს_ინდექსი == A+1 then
    შევინახოთ მიღებული კლასი;
  else
  if სიმბოლოს_ინდექსი == A then
    rec(A+1, 0, სიხშირეები+{დარჩენილი სიგრძე});
  else
    for i=0 to დარჩენილი_სიგრძე do
      rec(სიმბოლოს_ინდექსი+1, დარჩენილი_სიგრძე–i, სიხშირეები+{i});
end;

ამ ფსევდოკოდში ყოველი სიმბოლოსთვის ვარჩევთ, რა იქნება მისი სიხშირე. ბოლო სიმბოლოს სიხშირე აუცილებლად ავსებს სიმბოლოების ჯამურ რაოდენობას სიტყვის სიგრძემდე. პროცესი მთავრდება მაშინ, როდესაც სიღრმე (A+1) გახდება, ანუ მოცემული ანბანის ყველა სიმბოლოს სიხშირე დავაფიქსირეთ. იგულისხმება, რომ ეს პროცედურა გამოიძახება პარამეტრებით (1, N, {}).

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

1) განვიხილოთ სტრიქონი როგორც N-ელემენტიანი მიმდევრობა. როგორც ცნობილია, N–ელემენტიანი მიმდევრობის გადანაცვლებათა რაოდენობა არის N!. მაგრამ ჩვენს შემთხვევაში ზოგიერთი გადანაცვლება ერთმანეთის ტოლფასია, ანუ ისეთები, სადაც ადგილები ერთსადაიმავე სიმბოლოს შესაბამისმა ელემენტებმა გაცვალეს. თუ აღვნიშნავთ N_A–თი სტრიქონში 'A'–ების სიხშირეს და ანალოგიურად შემოვიღებთ N_B, N_C, N_D სიხშირეებს, მაშინ კონკრეტული ინდექსების მიმდევრობისთვის მისი N_A!*N_B!*N_C!*N_D! ცალი გადანაცვლება შედეგად მოგვცემს ზუსტად იგივე სტრიქონს. ამიტომ საწყისი N! გადანაცვლებიდან მხოლოდ N! / (N_A!*N_B!*N_C!*N_D!) იქნება განსხვავებული. ასეთი ფორმულით რაოდენობების დათვლისას ჩვენ გვიწევს გაყოფის ოპერაციის გამოყენება. რადგან პასუხი არ ეტევა 8–ბაიტიან მონაცემთა ტიპშიც კი, გაყოფას პირდაპირ ვერ მოვახდენთ. ამ ამოცანაში შეგვიძლია ფაქტორიალები დავშალოთ მარტივ მამრავლებად და გამრავლების დროს შევკრიბოთ მათი ხარისხები, ხოლო გაყოფის დროს კი გამოვაკლოთ.

2) დავაკვირდეთ, რომ სტრიქონის N პოზიციიდან N_A პოზიციის შერჩევა 'A' სიმბოლოებისთვის შეიძლება C(N, N_A) სხვადასხვა ვარიანტით (იგულისხმება ჯუფთება). ამ არჩევნის გაკეთების შემდეგ, გვრჩება N-N_A ცალი პოზიცია, რომელზეც უნდა მოვათავსოთ N_B ცალი 'B', N_C ცალი 'C' და N_D ცალი 'D'. 'B'–ების განთავსების ვარიანტებია C(N-N_A, N_B), 'C'-ების C(N-N_A-N_B, N_C) და 'D'–ები კი ყოველთვის ცალსახად განლაგდება, იმიტომ რომ მეტი სიმბოლოები აღარ დაგვრჩა. ამგვარად, კონკრეტული N_A, N_B, N_C, N_D მნიშვნელობებისთვის შესაბამის ანაგრამათა კლასში იქნება C(N, N_A) * C(N-N_A, N_B) * C(N-N_A-N_B, N_C) ცალი სტრიქონი. C(i,j) კოეფიციენტები პასკალის სამკუთხედიდან ითვლება ფორმულით C(i,j)=C(i-1,j-1)+C(i-1,j), ანუ გაყოფას საერთოდ არ საჭიროებენ.

დავადგინეთ რა ანაგრამების კლასები და მათში სტრიქონების რაოდენობა, საწყის ამოცანას ამოვხსნით დინამიური პროგრამირების საშუალებით. დავარქვათ i-ურ კლასში სტრიქონების რაოდენობას X_i (დავნომროთ კლასები 1–დან). შემოვიღოთ ორგანზომილებიანი ცხრილი ANS(i,j), რომლის მნიშვნელობაა "რამდენნაირად შეიძლება პირველი i ცალი ანაგრამათა კლასიდან ზუსტად j ცალი სტრიქონის არჩევა ისე, რომ ყველა განსხვავებულ კლასებს ეკუთვნოდეს". გასაგებია, რომ ANS(i,0)=1 ნებისმიერი i-სთვის და ANS(0,j)=0 ნებისმიერი დადებითი j-ისთვის. შეგვიძლია შევნიშნოთ შემდეგი რეკურენტული ფორმულა:

ANS(i,j) = ANS(i-1,j) + ANS(i-1,j-1)*Xi, თუ 0 < i <= |X|, 0 < j <= K

ლოგიკა ასეთია: პირველი i ცალი ანაგრამათა კლასიდან j ცალი სტრიქონის არჩევა (აქ და შემდგომში – კლასიდან 2 ცალის აურჩევლად) შეიძლება წარმოვადგინოთ როგორც პირველი (i-1) კლასიდან j სტრიქონის აღება, ხოლო i-ურიდან სტრიქონის არაღება, ან როგორც პირველი (i-1) კლასიდან (j-1) სტრიქონის აღება და i–ური კლასიდან 1 სტრიქონის აღება. ვინაიდან i-ურ კლასში X_i ცალი სტრიქონია, ნებისმიერი მათგანის აღება ახალ ვარიანტს ქმნის. ყველა ANS(i,j) უნდა ვითვალოთ M-ის მოდულით, იმიტომ რომ რიცხვები სწრაფად იზრდება.

რაკი i–ს მნიშვნელობა [0,|X|], ხოლო j–ს [0,K] შუალედშია მოთავსებული და ყოველი ინდექსების წყვილისთვის O(1) ოპერაცია ხდება, ალგორითმის ამ ნაწილის სირთულეა O(|X|*K).

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