Fişierul intrare/ieşire:numinum.in, numinum.outSursăONI 2018, clasa a 9-a, ziua 2
AutorCiprian ChescaAdăugată detheodor.moroianuTheodor Moroianu theodor.moroianu
Timp execuţie pe test0.2 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Numinum

Se consideră următoarea structură de date:

  • În vârful structurii se găseşte fracţia  \frac{1}{1}
  • Din fiecare vârf în care se găseşte fracţia  \frac{p}{q} se formează alte două fracţii trasând câte 2 segmente de dreaptă astfel: către stânga fracţia  \frac{p}{p+q} şi către dreapta fracţia  \frac{p+q}{q}.

Date de intrare

Pe prima linie a fişierului de intrare numinum.in se găseşte un număr natural N.
Pe fiecare dintre următoarele N linii se găsesc câte 4 numere naturale xi, yi, ai, bi, 1 ≤ i ≤ N, despărţite prin câte un spaţiu unde xi, yi reprezintă numărătorul, respectiv numitorul primei fracţii de pe linia i+1, iar ai , bi reprezintă numărătorul, respectiv numitorul celei de-a doua fracţii de pe linia i+1.

Date de ieşire

Fişierul de ieşire numinum.out va conţine N linii. Pe linia i se va scrie numărul minim de segmente de dreaptă necesare pentru a conecta, pe structura dată, fracţia xi/yi cu fracţia ai/bi.

Restricţii

  • 1 ≤ N ≤ 10000
  • 1 ≤ xi, yi, ai, bi ≤ 109

Exemplu

numinum.innuminum.out
1
4 3 2 5
6

Explicaţie

N = 1
x1 = 4, y1 = 3, a1 = 2, b1 = 5
Pentru a conecta fracţia  \frac{4}{3} cu fracţia  \frac{2}{5} avem nevoie de minim 6 segmente, după cum urmează:
4/3 -> 1/3 -> 1/2 -> 1/1 -> 2/1 -> 2/3 -> 2/5

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?