| Fişierul intrare/ieşire: | poarta2.in, poarta2.out | Sursă | OJI 2019, clasa a 7-a |
| Autor | Filonela Balasa | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Poarta2
Sindbad a descoperit un recipient care conține o poțiune magică și o inscripție care descrie cum se poate deschide poarta unui templu. Urmând instrucțiunile din inscripție, Sindbad a ajuns la un tunel acoperit cu dale pătrate, aliniate astfel încât formează linii și coloane. Tunelul are mai multe linii, iar pe fiecare linie sunt câte N dale. Dalele din tunel sunt numerotate începând cu 1, astfel încât, parcurgându-le linie cu linie și fiecare linie de la stânga la dreapta, se obține un șir strict crescător de numere naturale consecutive.
Sindbad se află la intrare, înaintea primei linii. Pentru a deschide poarta templului, el trebuie să ajungă pe dala numerotată cu P, călcând pe un număr minim de dale. Dacă există mai multe astfel de soluții, o va alege pe cea pentru care consumul total de picături de poțiune magică este minim.
Pe parcursul deplasării el trebuie să respecte următoarele reguli:
- de la intrare, poate sări pe orice dală aflată pe prima line, fără a consuma poţiune magică;
- de pe o dală numerotată cu X, Sindbad poate sări fie pe dala numerotată cu X+1, consumând o picătură de poțiune magică, fie pe dala numerotată cu 2*X, consumând două picături de poțiune magică.
Scrieţi un program care citeşte valorile N și P cu semnificația din enunț și rezolvă următoarele cerințe:
- afișează numărul minim de dale pe care trebuie să calce pentru a deschide poarta;
- afișează numărul natural T, reprezentând numărul minim de picături de poțiune magică necesare pentru deschiderea porții.
Date de intrare
Fișierul de intrare poarta2.in conține pe prima linie un număr natural C reprezentând cerința din problemă care trebuie rezolvată ($1$ sau 2). Pe a doua linie se află numărul natural N, iar pe a treia linie se află numărul natural P cu semnificația din enunț.
Date de ieşire
Fişierul de ieşire poarta2.out va conţine o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerinţa C.
Restricții și precizări
- 2 ≤ N < 104
- P este număr natural nenul cu cel mult 1000 de cifre; pentru o parte dintre teste, valorând în total 60 de puncte, P are cel mult 18 cifre.
- Recipientul conţine o cantitate suficientă de poţiune magică.
- Pentru rezolvarea cerinței 1 se acordă maximum 60 de puncte, iar pentru rezolvarea cerinței 2 se acordă maximum 30 de puncte. Sunt 10 puncte din oficiu (a caror teste corespund cu primul exemplu).
Exemple
| poarta2.in | poarta2.out | Explicatie |
|---|---|---|
| 1 5 9 | 3 | Tunelul are 5 dale pe fiecare linie. Sindbad trebuie să ajungă pe dala numerotată cu 9. Numărul minim de dale pe care trebuie să calce pentru a ajunge pe dala 9 pentru a deschide poarta este 3. De pe margine poate sări: * pe dala numerotată cu 4 (consumă 0 picături de poțiune magică); * de pe dala numerotată cu 4 pe cea numerotată cu 8 (consumă 2 picături de poțiune magică); * de pe dala numerotată cu 8 pe cea numerotată cu 9 (consumă 1 picătură de poțiune magică). |
| 2 5 9 | 3 | Pentru a ajunge pe dala numerotată cu 9 are nevoie de cel puțin 3 picături de poțiune magică |
