Fişierul intrare/ieşire:poarta2.in, poarta2.outSursăOJI 2019, clasa a 7-a
AutorFilonela BalasaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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:

  1. afișează numărul minim de dale pe care trebuie să calce pentru a deschide poarta;
  2. 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.inpoarta2.outExplicatie
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ă
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?