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

თუ ვიცით, რომ სართულის ნამდვილი ნომერია K, და მისი ნომერი მე-13 კორპუსის მაცხოვრებელდთა სისტემაში არის P, მაშინ K+1-ე სართულის ნომერი იქნება:

• P+1, თუ P+1 არ არის 13-ის ჯერადი
• P+2, თუ P+1 არის 13-ის ჯერადი.

ერთ-ერთი ამოხსნა:

int solution(int n){
	int ans=0;
	for(int i=1;i<=n;i++){
		ans++;
		if(ans%13==0)ans++;
	}
    return ans;
}

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

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

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

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

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

კონტაქტების სიაში ციკლურად შეგვიძლია მოძრაობა. თუ მიღებული გვაქვს კონტაქტების სია, რომელშიც N კონტაქტია და ჩვენი საძებნი კონტაქტის ინდექსია K, მაშინ მისი მოძებნის დრო იქნება მინიმალური K - 1 და N – K + 1 შორის.

ამოცანის ამოხსნის ერთ-ერთი ალგორითმი შემდეგია: ვარჩევთ საძებნ კონტაქტს (O(N)) და მის ყველა პრეფიქსს (O(S) , სადაც S კონტაქტის მაქსიმალური სიგრძეა) . მიღებული სიისთვის ძებნის დრო იქნება პრეფიქსის ასაკრეფად საჭირო დროს დამატებული ამ სიაში ჩვენი კონტაქტის მოძებნის დრო. ამ დროებიდან ვირჩევთ მინიმალურს. თითოეული კონტაქტის მოძებნისთვის საჭირო დროებიდან მაქსიმალური იქნება ამოცანის პასუხი.

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

ალგორითმის მუშაობის სირთულეა O(N^2 * S).

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

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

მთლიანი სიმრავლის (განვიხილავთ, როგორც ინტერვალი [1,N]) პასუხის დასათვლელად ჯერ დავითვალოთ პასუხი მასზე პატარა ინტერვალებისათვის და შემდეგ შევაერთოთ. ვთქვათ, გვაქვს დასათვლელი პასუხი ინტერვალზე [i,j]. ცხადია, რომ თუ ამ ინტერვალის ზომა K-ს არ აღემატება, ინტერვალი უკვე დაყოფილია და შესაბამისად დაყოფის ფასია 0. თუ ინტერვალის ზომა (ანუ j-i+1) აღემატება K-ს, მაშინ ჩავთვალოთ, რომ ყველა უფრო ნაკლები ზომის შუალედისათვის პასუხი დათვლილი გვაქვს და გადავარჩიოთ [i,j] შუალედის ნებისმიერი შესაძლო გაყოფა:

A=[i…i+1] , B= [i+2...j]
A= [i...i+2], B= [i+3...j]
...
A= [i...j-2], B= [j-1...j]

[i,j] შუალედისათვის ფასი, დაემთხვევა ერთ–ერთი გაყოფით მიღებული ორი ქვეინტერვალის ვარიაციათა ნამრავლს პლიუს მათი ფასების ჯამს. საინტერესოა მხოლოდ ის გაყოფა, სადაც ეს ჯამი მინიმალურია. ალგორითმი შემდეგი იქნება:

ჯერ დავითვალოთ ყველა შესაძლო 2 ან მეტ ელემენტიანი ინტერვალისათვის ვარიაციები (მაქსიმუმს მინუს მინიმუმი). შემდეგ გადავიდეთ ამოცანის პასუხის დათვლაზე: განვიხილოთ ყველა [i,j] ინტერვალი – ამ ინტერვალებს მოვყვეთ სიგრძის ზრდადობის მიხედვით. თითოეულისათვის დავითვალოთ მინიმუმი პასუხი[i,D] + პასუხი[D+1,j] + ვარიაცია[i,D] * ვარიაცია[D+1,j] რიცხვებს შორის, სადაც i+1 ≤ D < j-1.

ამოცანის პასუხი იქნება [1,N] ინტერვალისათვის გამოთვლილი რიცხვი.

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

თავდაპირველად გადავარჩიოთ S-ის ყველა გამყოფი speed, რომელიც გრენდაიზერის სიჩქარე იქნება, ხოლო power = S / speed კი მისი სიმძლავრე. ყოველი ასეთი წყვილისათვის, რომელთა რაოდენობა იქნება d(S), ანუ S-ის გამყოფთა რაოდენობა, განვიხილოთ შემდეგი ალგორითმი:

პირველი წვეროდან(დედამიწიდან) ყველა დანარჩენ წვერომდე(პლანეტამდე) ვიპოვოთ ამ წვერომდე მისასვლელი მინიმალური დრო(გარკვეულ შეზღუდვებში, რომელსაც შემდეგ ვიტყვით). თუ ამ მინიმალურ დროში ამ წვეროში power-ზე მეტი თეფში გაჩნდა მაშინ ეს წვერო მიუღწევადი ყოფილა საწყისი წვეროსათვის. საწყისი წვეროდან მინიმალური დროების საპოვნელად განვიხილოთ კარგად ცნობილი დეიქსტრას ალგორითმის მოდიფიკაცია. თავიდან ვართ საწყის წვეროში და დანაჩენი წვეროები მიუღწევადია. ყოველ ბიჯზე განვიხილოთ ისეთი წვერო რომელში მისასვლელი დროც არის საუკეთესო და ეს წვერო ჯერ არ განგვიხილავს. ვთქვათ მისი ნომერია v. განვიხილოთ ისეთ u წვეროთა მიმდევრობა რომლამდე მინიმალური მანძილი ჯერ არ გვაქვს დადგენილი და (v,u) წიბო არსებობს. mintime(x)-ით აღვნიშნოთ x წვერომდე მინიმალური დრო, ხოლო edge(x,y)-ით კი x და y წვეროებს შორის მანძილი.

მაშინ, თუ

(mintime(v) + speed / edge(v,u)) * (B[u]) + A[u] > power

v წვეროდან u წვეროში ვერ მოვხვდებით, რადგანაც მაგ დროისთვის მფრინავი თეფშების რაოდენობა გრენდაიზერზე მეტი იქნება, ხოლო თუ ეს უტოლობა არ სრულდება, mintime(u) გავხადოთ მინიმალური mintime(u)-სა და (mintime(v)+speed/edge(v,u)+1)-ს შორის. მთელი მიმდევრობის განხილვის შემდეგ v წვერო განხილულ წვეოებში ჩავაგდოთ და მეტად აღარ განვიხილოთ. ყოველ ბიჯზე ასეთი მინიმალური დროის მქონე v წვეროს საპოვნელად გამოვიყენოთ set ან priority queue-ს სტრუქტურა, უფრო დაწვრილებით იხილეთ შემდეგი გვერდი http://e-maxx.ru/algo/dijkstra_sparse.

თუ საბოლოოდ მივიღეთ რომ N წვერო მიღწევადია რაიმე დროში, მაშინ ეს კონფიგურაცია speed-ისა და power-ის გვაძლევს პასუხს, ანუ საბოლოო პასუხი გავზარდოთ ერთით. ამ ალგორითმის მუშაობის დროა O(d(S)*M*log(N)). 10^9 მდე მაქსიმალური d(S) არის 1344, და ალგორითმის მუშაობა თავისუფლად ეტევა რამოდენიმე წამში.

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