Nu aveti permisiuni pentru a descarca fisierul grader_test1.ok
Diferente pentru problema/floare intre reviziile #25 si #5
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="floare") ==
Intr-o zi cand se plictiseau, Ana si prietenele ei au inventatunnoujoc, pe care l-au jucat de$T$ ori. Fetele au o floare cu $N$ petale si la o mutare au voie sa rupa minim unasi maxim $K$ dintre ele. Traditia spune ca norocoasa care ia ultimele petale ale florii va primi $A$~0~trandafiri rosii, cea care ar fi trebuit sa mute urmatoarea va primi $A$~1~trandafiri rosii si asa mai departe pana la cea care a mutat exact inainte de castigatoare, care primeste $A$~M-1~trandafiri. Ana poate stabili ordinea in care fetele vorrupe petalele. Ajutati-o, pentru fiecaredintrecele $T$jocuri,sa castige cat maimultitrandafiri.
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 maxim $K$ dintre ele. Traditia spune ca norocoasa care ia ultimele petale ale florii va primi $M$ trandafiri rosii, cea care ar fi trebuit sa mute urmatoarea va primi $M - 1$ trandafiri rosii si asa mai departe pana la cea care a mutat exact inainte de castigatoare, care primeste $1$ trandafir. Ana poate stabili ordinea in care fetele vor intra in joc. Ajutati-o sa castige cei $M$ trandafiri.
h2. Date de intrare
Fişierul de intrare $floare.in$ continepe prima liniecele $3$ numere, $M$ - numarul de jucatoare, $K$ - numarulmaximde petalecare pot fi luate la o mutaresi $T$ - numarulde jocuri. Pe ceade-a doua liniesegaseste sirul$A$. Pefiecaredintreurmatoarele$T$linii se gaseste$N$- numarul de petale ale florii pentru jocul respectiv.
Fişierul de intrare $floare.in$ contine cele $3$ numere, $M$ - numarul de jucatoare, $N$ - numarul de petale si $K$ - numarul maxim de petale care pot fi luate la o mutare
h2. Date de ieşire
În fişierul de ieşire $floare.out$ se vorafla$T$numere, pozitia fetei castigatoarepentrufiecare dintrecele $T$ runde dejoc.
În fişierul de ieşire $floare.out$ se va afla un singur numar, pozitia fetei care va castiga jocul.
h2. 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$
* $1 ≤ M ≤ 200000$ * $1 ≤ N ≤ 200000$ * $1 ≤ K ≤ N$ * Se stie ca fiecare fata vrea sa maximizeze numarul de trandafiri pe care ii va primi la sfarsit * Pentru teste in valoare de cel putin $40$ de puncte $N ≤ 1000$
h2. Exemplu table(example). |_. floare.in |_. floare.out |
|2 3 1 2 1 6
|2 6 3
| 1 | h3. Explicaţie
O strategie castigatoare pentru prima jucatoare in exemplul de mai sus ar putea fi: ia $2$ petale,floarearamane cu $4$petale. De aici oricate petale ar rupea $2$-a jucatoare($1$, $2$ sau $3$),prima jucatoare va putea sa ia tot ce a ramas.
O strategie castigatoare pentru prima jucatoare in exemplul de mai sus ar putea fi: ia $2$ petale, a $2$-a jucatoare ramane cu $4$. De aici oricate petale ar rupe ($1$, $2$ sau $3$) prima jucatoare va putea sa ia tot ce a ramas.
== include(page="template/taskfooter" task_id="floare") ==
Nu exista diferente intre securitate.
Diferente intre topic forum:
4267