| Fişierul intrare/ieşire: | transformari.in, transformari.out | Sursă | Selectie Girls Programming Camp |
| Autor | Paul-Dan Baltescu | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | transformari.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).
