ლაზერი

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

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

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

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

წყარო: IBSU, 2014, ზამთრის ოლიმპიადა, X-XII


 

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

სათამაშო ველი წარმოადგენს უსასრულო ჰორიზონტალურ ლენტას, რომელიც მარცხნიდან მარჯვნივ მთელი რიცხვებით გადანომრილ უჯრებადაა დაყოფილი (იხილეთ ნახატი ქვემოთ). თავდაპირველად უარყოფითნომრებიან უჯრებში თქვენს განკარგულებაში მყოფი მონსტრების არმიაა განლაგებული, რომელთაგან თითოეულს სიცოცხლეთა გარკვეული რაოდენობა გააჩნია. კერძოდ, უჯრებში ნომრებით -1, -2, . . . , -K განლაგებულ მონსტრებს 1 სიცოცხლე გააჩნიათ, შემდეგი K რაოდენობის უჯრაში (ნომრებით -(K+1), -(K+2), . . . , -2K) განლაგებულ მონსტრებს 2 სიცოცხლე და ა.შ. ამგვარად, ყოველი მთელი დადებითი i რიცხვისათვის უჯრაში ნომრით -i თავდაპირველად იმყოფება მონსტრი, რომელსაც i/k (განაყოფი დამრგვალებული მთელამდე მეტობით) რაოდენობის სიცოცხლე გააჩნია. ამას გარდა, ლენტის გასწვრივ განლაგებულია ორი კოშკი, რომელთაგან თითოეულიდან ლაზერის სხივის საშუალებით ლენტის გარკვეული მონაკვეთი კონტროლდება: პირველი კოშკიდან კონტროლდება ყველა უჯრა A-დან B-მდე ჩათვლით, ხოლო მეორედან - ყველა უჯრა C-დან D-მდე ჩათვლით (0 ≤ A ≤ B < C ≤ D).

მაგალითად, როცა K=3, A=B=1, C=3 და D=4, საწყის პოზიციას ასეთი სახე ექნება:

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

თამაში მთავრდება (D + 1)-ე უჯრაში მონსტრის პირველი გამოჩენისთანავე.

როგორც ალბათ უკვე შეამჩნიეთ, თამაშის მთავარი პრობლემა იმაშია, რომ მოგებისათვის შეიძლება ღილაკზე საკმაოდ დიდი რაოდენობით დაჭერა გახდეს საჭირო. ამიტომ, თამაშის შემქმნელებმა ზოგიერთი განსაკუთრებით რთული დონისათვის ასაკობრივი შეზღუდვების განსაზღვრა გადაწყვიტეს. რადგანაც ისინი ამჟამად სხვა თამაშის შექმნით არიან დაკავებული, თქვენ გთხოვეს დახმარება იმის განსაზღვრაში, თუ ღილაკზე რამდენი დაჭერა იქნება საჭირო გამარჯვებისათვის, როცა თამაშის სირთულის დონე აღიწერება რიცხვებით: K, A, B, C და D.

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

სტანდარტული შეტანის ერთადერთ სტრიქონში მოცემულია თითო ჰარით გამოყოფილი 5 მთელი დადებითი K, A, B, C და D რიცხვი (1≤K≤109, 0≤A≤B<C≤D≤109).

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

სტანდარტული გამოტანის ერთადერთ სტრიქონში გამოიტანეთ ღილაკზე დაჭერათა გამარჯვებისათვის საჭირო რაოდენობა თამაშის სირთულის მოცემული დონისათვის.

 

 




მაგალითები

შესატანი მონაცემები
2 0 0 1 1 დაკოპირება
გამოსატანი მონაცემები
7 დაკოპირება
შესატანი მონაცემები
3 1 1 3 4 დაკოპირება
გამოსატანი მონაცემები
13 დაკოპირება
შესატანი მონაცემები
1 2 3 7 11 დაკოპირება
გამოსატანი მონაცემები
17 დაკოპირება

შენიშვნა

 

საწყისი პოზიცია:

პირველი დაჭერის შემდეგ:

მეორე დაჭერის შემდეგ:

მესამე დაჭერის შემდეგ:

მეოთხე დაჭერის შემდეგ:

მეხუთე დაჭერის შემდეგ:

 

შეფასება:

ტესტების 30%-ში 1K≤103, 0AB<CD103;

ტესტების 30%-ში 1K105, 0AB<CD105.