Fişierul intrare/ieşire:floare.in, floare.outSursă.com 2009, Runda 1
AutorCezar MocanAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.infloare.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content