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

ამოხსნა ძალიან მოკლედ შეიძლება ჩამოყალიბდეს: ციკლით მივყვეთ გვერდებს 1-დან k-1 -მდე. შემოვიღოთ მთვლელი, რომლის საწყისი მნიშვნელობაა 0 და ყოველი ისეთი გვერდისათვის, რომელიც არ შედის (a1, a2, …, am) მასივში (ანუ გვერდისათვის, რომელზეც კროსვორდია განთავსებული), ეს ცვლადი გავზარდოთ 5-ით. საბოლოო პასუხი იქნება ამ ცვლადში მიღებული რიცხვი.

გასათვალისწინებელი ფაქტები მონაცემთა წაკითხვისას:

შეიძლება შემომავალი ფაილი ყოველთვის 2 სტრიქონს არ შეიცავდეს (როდესაც m=0 ფაილი შედგება მხოლოდ 1 სტრიქონისაგან). ასე რომ, ჯერ ორი სტრიქონის წაკითხვა და შემდეგ მათზე ოპერაციები სასურველ შედეგამდე ვერ მიგვიყვანს. უნდა წავიკითხოთ პირველი სტრიქონის მონაცემები და თუ m≠0, მეორე სტრიქონიდან m ცალი რიცხვი.

Pascal ენაში წაკითხვისათვის არ გამოგვადგება readln ფუნქცია, რადგან ის თითო ხაზზე მხოლოდ ერთ მონაცემს წაიკითხავს. მის ნაცვლად უნდა გამოვიყენოთ read.

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

დავიწყოთ იმით, რომ ამოცანის პასუხი საკმაოდ მცირეა. N ≤ 100 რიცხვებში მაქსიმალური პასუხია 95 N=95-ისთვის. ამის დანახვის შემდეგ ამოცანა დადის ჩვეულებრივ სიმულაციაზე: ვახორციელოთ პირობაში მითითებული ოპერაცია მანამ, სანამ გროვებში ერთი ფერის ჩიპები არ დარჩება. ამის მოდელირება მარტივად შეიძლება 3 მასივის საშუალებით: A და B მასივები საწყისი გროვები იქნება, C მასივი კი მათი შეერთებით მიღებული დიდი გროვა, რომლიდანაც შემდეგ ახალ A და B მასივებს მივიღებთ.

პასუხზე რაიმე ზედა ზღვარი როგორ უნდა დავამტკიცოთ, არ ვიცი. შემოთავაზებები თუ იქნება, კომენტარებში ველით :) ისე კი პასუხების მიმდევრობა აქაა აღწერილი: http://oeis.org/A003558
როგორც ხედავთ, კონკრეტული N-ისთვის პასუხია ისეთი უმცირესი M, რომ 2^M mod (2N+1) 1-ის ან 2N-ის ტოლია.

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

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

გადავარჩიოთ პასუხში რა მიმდევრობით უნდა შეგვხვდეს მოცემული სიტყვები (სიტყვების პირველი ასოები) და თითოეული ვარიანტისათვის დავითვალოთ მინიმალური სიგრძის სიტყვა.

მაგალითის ტესტისათვის მოგვიწევს 6 ვარიანტის განხილვა:

bi lisi tbil
bi tbil lisi
lisi bi tbil
lisi tbil bi
tbil bi lisi
tbil lisi bi

მაგალითად, ვთქვათ ვითვლით პასუხს, როდესაც ჯერ უნდა შეგვხვდეს სიტყვა “lisi”, შემდეგ “tbil” და შემდეგ “bi”.

დავიწყეთ: თავიდან დავწეროთ სიტყვა “lisi”. შემდეგ მას უნდა მივუერთოთ სიტყვა „tbil”. “lisi”-ს „tbil”-ს ვუერთებთ ისე, რომ მიღებული სიტყვა შეიცავდეს lisi-საც და tbil-საც (ამ მიმდევრობით) და თან იყოს მინიმალური სიგრძის. განვიხილოთ ეს პროცედურა განზოგადებულად, ვთქვათ A სტრიქონს ვუერთებთ B სტრიქონს.

გვაქვს 3 შემთხვევა:

1) თუ A სტრიქონი შეიცავს B სტრიქონს, მაშინ პასუხია A (რადგან A სტრიქონი შეიცავს A-საც და B-საც ამ მიმდევრობით)

2) თუ რომელიღაც i-სათვის A-ს i-ური სუფიქსი (ანუ სიტყვა სიმბოლოებით A[i],A[i+1],…) არის B-ს პრეფიქსი (ანუ შედის B-ში და თანაც დაწყებული ნულოვანი ინდექსიდან), მაშინ A და B-ს გაერთიანება იქნება A+B-დან ამოგდებული მათი საერთო ნაწილი - A-ს i-ური სუფიქსი. თუ ასეთი i რამდენიმეა, ჩვენ გვაინტერესებს ისეთი, რომ მიღებული პასუხი იყოს რაც შეიძლება მცირე სიგრძის, ანუ i იყოს მინიმალური. (პროცედურის ზუსტი ამოხსნისათვის i უნდა იყოს ისეთი, რომ B იწყებოდეს A-ში ბოლოს ჩასმული სიტყვის შემდეგ, მაგრამ თავდაპირველი ამოცანის ამოსახსნელად ეს შეზღუდვა არ გვჭირდება).

3)სხვა შემთხვევაში პასუხია A+B

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

“tbil” და „bi”-ს შეერთებით მივიღებთ “tbil”-ს, მასზე “lisi”-ს შეერთებით მივიღებთ „lisitbil”-ს.

სწორი პასუხის შესაბამისი გადანაცვლებაა (tbil,bi,lisi).

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

დავაკვირდეთ, როგორი სტრატეგიით უნდა იმოძრავოს მთავარმა გმირმა (კინაღამ მაგასაც მანაო დავარქვი) ოპტიმალურ შემთხვევაში. არის სულ ორი ვარიანტი:

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

2) მან იგივე პროცესი უნდა განახორციელოს, ოღონდ მეორე მოსაუბრისგან დაიწყოს.

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

ამისთვის განვიხილოთ მიმართული გრაფი, რომლის წვეროები თემებს შეესაბამება და წიბო i-

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

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

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

ვნახოთ ზოგადი სურათი იმისა, თუ ვინ ვერ გადარჩება ბოლოს. ქეიფის წამომწყებთა შორის n-ურ სახლში ხვდებიან მხოლოდ n-ის გამყოფები, ხოლო ამ უკანასკნელებს კი მიჰყავთ მათი ჯერადები. შესაბამისად, n-ურ სახლში ხვდება n-ის გამყოფების (1-ის გარდა) ჯერადები. ეს ბოლო განსაზღვრება შეესაბამება არათანამარტივობის განმარტებას.

დასათვლელი გვაქვს a-დან b-მდე ისეთი რიცხვების საშუალო არითმეტიკული, რომლებიც n-ურ სახლში არ მოხვედრილან, ანუ n-თან ურთიერთმარტივები არიან. ერთადერთი გასათვალისწინებელია ის, რომ n-ური პერსონაჟიც ბოლოს გადარჩა.

საშუალო არითმეტიკულის დასათვლელად დავითვალოთ მათი ჯამი და რაოდენობა. ამისათვის დაგვჭირდება ე.წ. „ჩართვა-ამორთვის“ (inclusion-exclusion) ალგორითმი. n-ის ყველა მარტივი გამყოფი აღვნიშნოთ p[1], p[2],…,p[m]-ით. მარტივია იმის მტკიცება, რომ m ≤ 13 (პირველი 14 მარტივი რიცხვის ნამრავლი უკვე აჭარბებს 10^15-ს, რომელიც n-ის ზედა ზღვარია). ჩვენ უნდა დავითვალოთ a-დან b-მდე ისეთი რიცხვების ჯამი და რაოდენობა, რომლებიც არ იყოფიან არც p[1]-ზე, არც p[2]-ზე და ა.შ. ალგორითმი შემდეგია:

ჯერ განვიხილოთ a-დან b-მდე ყველა რიცხვის ჯამი და რაოდენობა;
მათ გამოვაკლოთ შესაბამისად იმათი ჯამი და რაოდენობა, რომლებიც იყოფიან p[1]-ზე;
შემდეგ გამოვაკლოთ იმათი, რომლებიც იყოფიან p[2]-ზე,შემდეგ p[3]-ზე , ... p[m]-ზე.
ახლა მიმდინარე ჯამსა და რაოდენობაში ორჯერ გვაქვს გამოკლებული ისეთები, რომლებიც იყოფიან p[1]-სა და p[2]-ზე, ასევე p[1]-სა და p[3]-ზე და ა.შ. მიღებულ ჯამსა და რაოდენობას მივუმატოთ იმათი ჯამი და რაოდენობა, რომლებიც იყოფიან p[1]*p[2]-ზე, შემდეგ ისეთების, რომლებიც იყოფიან p[1]*p[3]-ზე და ა.შ. p[m-1]p[m]-მდე.

ამის შემდეგ ბიჯზე გამოვაკლებთ ყოველი 3-ეულისათვის ჯამებს და რაოდენობებს, შემდეგ მივუმატებთ 4-ეულისათვის და ა.შ. მანამ არ მივალთ m-ეულთან და მოქმედებები დამთავრდება.

ალგორითმის განხორციელებისათვის დაგვჭირდება შემდეგი ორი პროცედურა:

1. დავითვალოთ a-დან b-მდე ისეთი რიცხვების რაოდენობა, რომლებიც იყოფიან c რიცხვზე.

2. დავითვალოთ a-დან b-მდე ისეთი რიცხვების ჯამი, რომლებიც იყოფიან c რიცხვზე.

ორივე პროცედურა მარტივად იხსნება, განვიხილოთ მეორე და პირველი ანალოგიური იქნება. დავითვალოთ 1-დან b-მდე c-ს ჯერადი რიცხვების ჯამი და გამოვაკლოთ 1-დან (a-1)-მდე c-ს ჯერადი რიცხვების ჯამი. 1-დან k-მდე c-ს ჯერადი რიცხვების ჯამის დასათვლელად გამოვიყენოთ არითმეტიკული პროგრესიის ფორმულა.

c + 2c + … + (k div c) * c = (k div c) * (c + c * (k div c)) / 2

სადაც k div c არის k-ს c-ზე მთლად გაყოფისას მიღებული რიცხვი.

1-დან k-მდე c-ს ჯერადი რიცხვების რაოდენობაა k div c.

p[1],p[2],…,p[m] რიცხვების ყველა ქვესიმრავლის გადარჩევა იოლად ხდება ე.წ. „ბიტმასკებით“. ავიღებთ ორობით რიცხვებს 0-დან 2^m-მდე.

00000...000-ს შევუსაბამებთ მდგომარეობას, როდესაც p-სგან არცერთი არ გვაქვს აღებული
00000...001-ს შევუსაბამებთ მდგომარეობას, როდესაც p[m] არის აღებული მხოლოდ.
...
00000...011-ს - როდესაც აღებულია p[m-1]*p[m]
და ა.შ.

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

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