| Fişierul intrare/ieşire: | floare.in, floare.out | Sursă | .com 2009, Runda 1 |
| Autor | Cezar Mocan | Adăugată de |  Cezar Mocan •CezarMocan |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Floare
Intr-o zi cand se plictiseau, Ana si prietenele ei au inventat un nou joc, pe care l-au jucat de T ori. Fetele au o floare cu N petale si la o mutare au voie sa rupa minim una si maxim K dintre ele. Traditia spune ca norocoasa care ia ultimele petale ale florii va primi A0 trandafiri rosii, cea care ar fi trebuit sa mute urmatoarea va primi A1 trandafiri rosii si asa mai departe pana la cea care a mutat exact inainte de castigatoare, care primeste AM-1 trandafiri. Ana poate stabili ordinea in care fetele vor rupe petalele. Ajutati-o, pentru fiecare dintre cele T jocuri, sa castige cat mai multi trandafiri.
Date de intrare
Fişierul de intrare floare.in contine pe prima linie cele 3 numere, M - numarul de jucatoare, K - numarul maxim de petale care pot fi luate la o mutare si T - numarul de jocuri. Pe cea de-a doua linie se gaseste sirul A. Pe fiecare dintre urmatoarele T linii se gaseste N - numarul de petale ale florii pentru jocul respectiv.
Date de ieşire
În fişierul de ieşire floare.out se vor afla T numere, pozitia fetei castigatoare pentru fiecare dintre cele T runde de joc.
Restricţii si precizari
- 1 ≤ T ≤ 100
- 1 ≤ M ≤ 200 000
- 1 ≤ N ≤ 200 000
- 1 ≤ K ≤ 200 000
- Se stie ca fiecare fata joaca optim, adica vrea sa castige cat mai multi trandafiri
- Valorile din sirul A sunt distincte
- Pentru teste in valoare de cel putin 30 de puncte valorile pentru N vor fi mai mici sau egale cu 1 000
Exemplu
| floare.in | floare.out |
|---|---|
| 2 3 1 2 1 6 | 1 |
Explicaţie
O strategie castigatoare pentru prima jucatoare in exemplul de mai sus ar putea fi: ia 2 petale, floarea ramane cu 4 petale. De aici oricate petale ar rupe a 2-a jucatoare ( 1, 2 sau 3), prima jucatoare va putea sa ia tot ce a ramas.
