.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » nivfractie

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
nivfractie


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

O proprietate interesantă a fracţiilor ireductibile este că orice fracţie se poate obţine după următoarele reguli:
• pe primul nivel se află fracţia 1/1;
• pe al doilea nivel, în stânga fracţiei 1/1 de pe primul nivel, plasăm fracţia 1/2, iar în dreapta ei fracţia 2/1;
• pe fiecare nivel k se plasează sub fiecare fracţie i/j de pe nivelul de deasupra, fracţia i/(i+j) în stânga, iar fracţia (i+j)/j în dreapta.


Cerinţă

Dându-se o fracţie oarecare prin numărătorul şi numitorul său, determinaţi numărul nivelului pe care se află fracţia sau o fracţie echivalentă (având aceeaşi valoare) cu aceasta.

Date de intrare

Fişierul de intrare nivfractie.in conţine pe prima linie două numere naturale nenule N M, separate printr-un spaţiu, reprezentând numărătorul şi respectiv numitorul unei fracţii.

Date de ieşire

Fişierul de ieşire nivfractie.out va conţine o ingură linie, pe care va fi scris număr natural nenul, reprezentând numărul nivelului care corespunde fracţiei.

Restricţii

1 < N,M ≤ 2000000000 (două miliarde)

Exemple

nivfractie.innivfractie.out
13 8 6
12 8 3

autor: Prof. Ovidiu Domşa
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
Chestionare recomandate
surse trimise | ajutor