Fişierul intrare/ieşire:transformari.in, transformari.outSursăSelectie Girls Programming Camp
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Transformari

Fie (X, Y) o pereche de numere întregi oarecare. Asupra unei astfel de perechi putem aplica două tipuri de transformări, care au ca rezultat perechile (X, X+Y) sau (X+Y, Y).

Se dă un număr întreg N. Să se determine numărul minim de transformări necesare pentru a obţine o pereche de forma (x, N) sau (N, x), unde x poate fi orice număr întreg.

Date de intrare

Fişierul de intrare transformari.in conţine numărul întreg N.

Date de ieşire

În fişierul de ieşire transformari.out conţine numărul minim de transformări necesare pentru a ajunge la o pereche de forma dorită.

Restricţii

  • 1 ≤ N ≤ 1 000 000
  • Pentru 60% din teste N ≤ 2 000.
  • Întotdeauna se pleacă de la perechea (1,1).

Exemplu

transformari.intransformari.out
5
3
9
5

Explicaţie

Pentru primul exemplu o soluţie posibilă ar fi: (1, 1) -> (1, 2) -> (3, 2) -> (3, 5). Pentru cel de-al doilea exemplu, o soluţie posibilă ar fi: (1, 1) -> (2, 1) -> (2, 3) -> (2, 5) -> (2, 7) -> (2, 9).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content