Suntem în anul 1066. Regele viking, Harald al III-lea se pregăteşte să cucerească
Anglia. Va porni pe mare împreună cu înfricoşătoarea sa armată, la bordul a
nu mai puţin temutelor corăbii vikinge (longships).
În această campanie, va folosi doar corăbii noi, identice. Înainte de plecare,
trebuie să determine capacitatea de transport a noilor sale corăbii. Prin capacitate
de transport, el înţelege numărul maxim de vikingi pe care o corabie îi poate
transporta fără ca să se scufunde. Pentru aceasta, regele decide că C
corăbii şi V vikingi vor fi implicaţi
în testări. Va ordona mai multe lansări la apă. La fiecare lansare, o singură
corabie trece de pe uscat pe apă, cu n
vikingi la bord, unde n <= V.
Dacă numărul de vikingi depăşeşte capacitatea de transport a navei, atunci corabia
se scufundă. O corabie scufundată nu mai poate fi recuperată, în timp ce o corabie
care a fost lansată la apă şi nu s-a scufundat, poate fi din nou lansată la
apă. Când o corabie se scufundă, soldaţii de la bord înoată până la mal, astfel
încât pentru fiecare lansare, Harald are mereu la dispoziţie aceeaşi V
vikingi, din care alege n. Toţi
soldaţii se presupun a fi identici (greutate identică, desigur). Când o corabie
pluteşte, nici un viking nu poate să urce sau să coboare. Vikingii se îmbarcă
sau debarcă doar la mal, înaintea lansării la apă.
Regele Harald doreşte un plan care să-i permită să efectueze un număr minim
de lansări la apă, deoarece acestea sunt consumatoare de energie şi de timp,
ori ultimul mare rege viking se grăbeşte să-şi întâlnească destinul ...
Cerinţă
Se cere numărul minim necesar de lansări la apă, care permit identificarea cu
exactitate a capacităţii de transport a corăbiilor.
Date de intrare
Fişierul de intrare vikingi.in
conţine pe prima linie două numere naturale V
şi C, separate printr-un spatiu.
Date de
ieşire
Fişierul de ieşire vikingi.out
va conţine o singură
linie pe care va fi scris un număr natural L,
calculat pentru cazul cel mai defavorabil, reprezentând numărul minim de lansări
la apă în urma cărora se poate determina cu exactitate capacitatea unei corăbii.
Restrictii
si precizari
1 <= V <= 2500
1 <= C <= 2500
Toate bărcile
sunt identice. Aceasta presupune şi faptul că au aceeaşi capacitate de transport.
Pentru toate
datele de test, numărul V de
vikingi este suficient de mare pentru a se putea determina capacitatea corăbiilor.
Exemple
vikingi.in
vikingi.out
Explicaţie
7
2
4
Sunt necesare minimum patru lansări la apă pe cazul cel mai defavorabil
vikingi.in
vikingi.out
Explicaţie
5
1
5
Sunt necesare cel puţin cinci lansări în cazul cel mai defavorabil, cu câte
1, 2, 3, 4, 5 vikingi îmbarcaţi