== include(page="template/taskheader" task_id="transformari") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $transformari.in$ ...
Fişierul de intrare $transformari.in$ conţine numărul întreg $N$.
h2. Date de ieşire
În fişierul de ieşire $transformari.out$ ...
Î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ă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1 000 000$
* Pentru $60%$ din teste $N ≤ 2 000$.
* Întotdeauna se pleacă de la perechea $(1,1)$.
h2. Exemplu
table(example). |_. transformari.in |_. transformari.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
| 3 |
| 9
| 5
|
h3. 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)$.
== include(page="template/taskfooter" task_id="transformari") ==
