CosmoCraft#3971

CosmoCraft

1 saniyə

32 meqabayt

Asan

İki oyunçulu CosmoCraft oyununda siz rəqibinizi məğlub edəcək ordu qurmaq üçün iqtisadiyyatı idarə edirsiniz. Siz işçilərin, istehsal obyektlərinin və ordu bölmələrinin inşasına nəzarət edirsiniz; məqsəd bu resurslar arasında balans qurmaqdır. Oyun növbə ilə davam edir.

Hər işçi hər növbədə sizə $1$ dollar gəlir gətirir.
Hər istehsal obyekti sizə $1$ dollar qarşılığında ya bir işçi, ya da bir ordu bölməsi istehsal etməyə imkan verir. (Bir obyekt üçün hər növbədə yalnız $1$ ordu bölməsi və ya işçi istehsal edilə bilər.)
İstehsal obyektinin yaradılması $1$ dollar tələb edir.
Ordu bölmələri rəqiblə döyüşmək üçün lazımdır.

Siz oyuna $n$ işçi və $k$ istehsal obyektləri ilə başlayırsınız. Hər növbədə işçilərdən əldə etdiyiniz gəliri istənilən kombinasiyada işçilər, ordu bölmələri və istehsal obyektləri yaratmağa sərf edə bilərsiniz. Mövcud növbədə istehsal olunan işçilər növbəti turdan əvvəl gəlir gətirmir; eynilə, həmin turda yaradılan istehsal obyektləri də gələn turdan əvvəl aktiv olmur. İstifadə edilməmiş gəlir növbəti tura keçir.

Hər növbənin sonunda istehsal etdiyiniz bütün ordu bölmələri ilə rəqibə hücum edə bilərsiniz. Əgər sizdə rəqibdən qəti şəkildə çox ordu bölməsi varsa, rəqib dərhal məğlub olur və bölmələrin fərqi sizdə qalır. Əks halda, ordunuz məhv olur və rəqibdə həmin fərq qalır. (Rəqib bundan sonra əks-hücum edə bilər, lakin siz dərhal məğlub olmursunuz.) Oyun $t$ növbədən sonra bitir və adətən hər iki oyunçu bütün ordu bölmələri ilə hücum edir, daha böyük orduya sahib olan qalib gəlir.

Dostunuza qarşı oynayırsınız və artıq onunla bir çox dəfə oynamısınız ki, hər növbədə pulunu nəyə xərcləyəcəyini və nə vaxt hücum edəcəyini dəqiq bilirsiniz. Bunu nəzərə alaraq, ən yaxşı strategiya kimi müdafiəçi oynamağa qərar verirsiniz—siz hər hücumdan sağ çıxmaq və bu arada mümkün qədər böyük ordu toplamaq istəyirsiniz ki, oyunun sonunda əks-hücum edib (ümid edirik ki) qalib gələsiniz.

Bütün dostunuzun hücumlarından sağ çıxmaq şərti ilə oyunun sonunda nə qədər böyük bir orduya sahib ola bilərsiniz?

Giriş

Giriş bir neçə yoxlama halı (test case) ehtiva edir. Hər yoxlama halı üç tam ədəddən ibarət bir sətrlə başlayır:

n k t

burada $n$ ( $1 \leq n \leq 100$ 1 \le n \le 100) başlanğıc işçi sayıdır, $k$ ( $1 \leq k \leq 100$ 1 \le k \le 100) başlanğıc istehsal obyektlərinin sayıdır və $t$ ( $1 \leq t \leq 10000$ 1 \le t \le 10000) növbə sayıdır. Növbəti sətirdə $t - 1$ t-1 tam ədəd, $a_{i}$ a_i ( $0 \leq a_{i} \leq$ 0 \le a_i \le Max signed $64$ -bit tam ədəd), boşluqlarla ayrılmış şəkildə verilir. $i$ -ci tam ədəd rəqibinizin həmin növbədə hücumda istifadə etdiyi ordu bölmələrinin sayını göstərir. Giriş üç $0$ ilə bitən bir sətrlə başa çatır.

Çıxış

Hər yoxlama halı üçün oyunun sonunda sahib ola biləcəyiniz maksimum ordu bölməsi sayını çıxarın. Əgər sağ qalmaq mümkün deyilsə, $- 1$ çıxarın. Hər tam ədədi öz sətrində, boşluqsuz çıxarın və cavablar arasında boş sətir çap etməyin. Bəzi girişlər çox böyük cavablar yarada bilsə də, bütün hakim girişləri imzalanmış $64$ -bit tam ədədə sığacaq cavablar verəcək.

Nümunələr

Nümunə 1