Fişierul intrare/ieşire: | numinum.in, numinum.out | Sursă | ONI 2018, clasa a 9-a, ziua 2 |
Autor | Ciprian Chesca | Adăugată de | Theodor Moroianu •theodor.moroianu |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 131072 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Numinum
Se consideră următoarea structură de date:
- În vârful structurii se găseşte fracţia
- Din fiecare vârf în care se găseşte fracţia se formează alte două fracţii trasând câte 2 segmente de dreaptă astfel: către stânga fracţia şi către dreapta fracţia .
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.in | numinum.out |
---|---|
1 4 3 2 5 | 6 |
Explicaţie
N = 1
x1 = 4, y1 = 3, a1 = 2, b1 = 5
Pentru a conecta fracţia cu fracţia avem nevoie de minim 6 segmente, după cum urmează:
4/3 -> 1/3 -> 1/2 -> 1/1 -> 2/1 -> 2/3 -> 2/5