== include(page="template/taskheader" task_id="sotron1") ==
Sofia iubește șotronul și îl joacă în fiecare zi în spatele blocului. Șotronul poate fi reprezentat ca un șir de [*N*] pătrățele așezate în linie, numerotate de la 1 la [*N*].
Poveste și cerință...
Jocul Sofiei constă în mai multe ture de joc. La începutul fiecărei ture a jocului, Sofia se află în poziția de start, aflată imediat înaintea căsuței 1, și aruncă o piatră care pică pe una dintre căsuțele șotronului. Considerăm că numărul căsuței pe care a picat piatra este [*i*]. Fetița trebuie apoi să se deplaseze până la căsuța [*i*], efectuând unul sau mai multe salturi și să ia piatra. Cum Sofia se antrenează zilnic, a învățat deja să sară peste mai multe căsuțe, din căsuța numărul [*i*] poate sări pe căsuțele [*i*] + 1, [*i*] + 2 respectiv [*i*] + 3, însă nu poate sări pe căsuța [*i*] + 4 sau mai departe.
Regula jocului spune că pentru turele de joc care urmează, Sofia nu mai are voie să calce pe căsuța [*i*], aceasta fiind marcată ca interzisă. Dacă piatra cade din nou pe o căsuță marcată anterior ca interzisă, jocul se încheie imediat întrucât fetița nu mai poate călca pe acea căsuță.
De exemplu, dacă Sofia se află în căsuța 2 și căsuțele 3 și 4 sunt interzise, ea poate sări peste cele două direct la căsuța 5. Dacă însă și căsuța 5 ar fi interzisă, Sofia nu ar putea sări peste toate cele trei să ajungă la căsuța 6.
!>problema/sotron1?sotron11.jpg!
h2. Date de intrare
h2. Cerință
Fișierul de intrare $sotron1.in$ ...
Cunoscându-se numărul [*N*] de pătrățele ale șotronului, numărul [*Q*] de aruncări pe care le-ar putea efectua fetița și indicele căsuței pe care ar ateriza piatra la fiecare aruncare, determinați care este prima aruncare la care Sofia nu mai poate recupera piatra.
h2. Date de ieșire
h2. Date de intrare
În fișierul de ieșire $sotron1.out$ ...
Fișierul de intrare $sotron1.in$ conține pe prima linie numerele [*N*] și [*Q*] separate printr-un spațiu, având semnificația din enunț. Pe a doua linie un șir de [*Q*] numere naturale separate prin câte un spațiu reprezentând, în ordine, poziția căsuței în care va pica piatra în cadrul fiecărei aruncări.
h2. Restricții
h2. Date de ieșire
* $... ≤ ... ≤ ...$
Fișierul de ieșire $sotron1.out$ va conține un singur număr, reprezentând răspunsul determinat. Dacă Sofia poate efectua toate turele jocului respectând regulile acestuia, atunci se va afișa [*Q*] + 1.
h2. Exemplu
h2. Restricții și precizări
table(example).
|_. sotron1.in |_. sotron1.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* 1 ≤ [*N*], [*Q*] ≤ 1 000 000
h3. Explicație
table(){width:auto; border:none; outline:none; border-collapse:collapse}.
|_. # |_. Punctaj |_. Restricții |
| 1 | 6 | [*N*], [*Q*] ≤ 100 |
| 2 | 17 | [*N*], [*Q*] ≤ 1 500 |
| 3 | 30 | [*N*], [*Q*] ≤ 50 000 |
| 4 | 47 | Fără restricții suplimentare |
h2. Exemple
table(example).
|_. $sotron1.in$ |_. $sotron1.out$ |_. Explicații |
| 15 10
1 14 3 12 13 4 5 7 12 10
| 8
| La a 8-a aruncare, cea când piatra aterizează
pe căsuța cu numărul 7, Sofia nu mai poate ajunge
la ea pentru că nu poate sări peste căsuțele 3-5.
|
| 15 10
1 14 3 12 14 4 5 7 13 10
| 5
| La a 5-a aruncare se repetă căsuța cu numărul 14,
deci Sofia nu poate ajunge la piatră.
|
| 15 10
1 14 3 12 13 4 7 11 10 9
| 11
| Sofia poate efectua toate turele, deci se
afișează [*Q*] + 1.
|
...
== include(page="template/taskfooter" task_id="sotron1") ==
== include(page="template/taskfooter" task_id="sotron1") ==
