Revizia anterioară Revizia următoare
| 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 inceput sa se joace. 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 AN-1 trandafiri. Ana poate stabili ordinea in care fetele vor intra in joc. Ajutati-o sa castige cei cat mai multi trandafiri.
Date de intrare
Fişierul de intrare floare.in contine pe prima linie cele 3 numere, M - numarul de jucatoare, N - numarul de petale si K - numarul maxim de petale care pot fi luate la o mutare.Pe cea de-a doua linie se gaseste sirul A.
Date de ieşire
În fişierul de ieşire floare.out se va afla un singur numar, pozitia fetei care va castiga jocul.
Restricţii si precizari
- 1 ≤ M ≤ 200000
- 1 ≤ N ≤ 200000
- 1 ≤ K ≤ N
- 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 N ≤ 1000
Exemplu
| floare.in | floare.out |
|---|---|
| 2 6 3 2 1 | 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.
