== include(page="template/taskheader" task_id="sotron1") ==
Poveste și cerință...
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*].
h2. Date de intrare
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.
Fișierul de intrare $sotron1.in$ ...
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ță.
h2. Date de ieșire
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.
În fișierul de ieșire $sotron1.out$ ...
!>problema/sotron1?sotron11.jpg!
h2. Restricții
h2. Cerință
* $... ≤ ... ≤ ...$
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 intrare
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. Date de ieșire
h2. Exemplu
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.
table(example).
|_. sotron1.in |_. sotron1.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h2. Restricții și precizări
h3. Explicație
* 1 ≤ [*N*], [*Q*] ≤ 1 000 000
...
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") ==
