Se consideră următoarea structură de date:

În vârful structurii se găsește fracția 1/1. Din fiecare vârf în care se găsește fracția p/q se formează alte două fracții trasând câte două segmente de dreaptă astfel: către stânga fracția p/(p+q) și către dreapta fracția (p+q)/q.

Cerința

Cunoscând numărătorul, respectiv numitorul a două fracții ireductibile diferite din structură, determinați numărul minim de segmente de dreaptă cu care putem conecta în structura dată, cele două fracții.

Date de intrare

Fișierul de intrare numinum.in conține pe prima linie numărul natural N. Pe fiecare dintre următoarele N linii se găsesc câte patru numere naturale x[i], y[i], a[i], b[i], 1 ≤ i ≤ N, despărțite prin câte un spațiu unde x[i], y[i] reprezintă numărătorul, respectiv numitorul primei fracții de pe linia i+1, iar a[i], b[i] 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 x[i] / y[i] cu fracția a[i] / b[i].

Restricții și precizări

1 ≤ N ≤ 10 000
1 ≤ x[i], y[i], a[i], b[i] ≤ 1 000 000 000, 1 ≤ i ≤ N

Exemplu

numinum.in

1
4 3 2 5

numinum.out

Explicație

N = 1, x[1] = 4, y[1] = 3; a[1] = 2, b[1] = 5. Pentru a conecta fracția 4/3 cu fracția 2/5 avem nevoie de minimum 6 segmente, după cum urmează: 4/3 → 1/3 → 1/2 → 1/1 → 2/1 → 2/3 → 2/5

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema numinum:

// prof. Chesca Ciprian
// sursa 100 p, O(log(min(a1,b1))+log(min(a2,b2)))

#include <fstream>
#include <cassert>

#define nmax 1000

using namespace std;

int main()
{
    long long a1,b1,a2,b2,T;
    long long w1[nmax],w2[nmax];
    long long d, i, j, k, c, r; // teorema impartirii cu rest
    long long k1,k2,ok1,ok2,s;

    ifstream fin("numinum.in");
    ofstream fout("numinum.out");
    fin >> T;
    assert(T>=1 && T<=10000);   

for(k=1;k<=T;k++)
    {
    fin >> a1 >> b1 >> a2 >> b2;
    assert(a1>=1 && a1<=1000000000);
    assert(b1>=1 && b1<=1000000000);
    assert(a2>=1 && a2<=1000000000);
    assert(b2>=1 && b2<=1000000000);

    // prima fractie.......................................................
    // determin fractia continua atasata primei fractii
    d = a1;i = b1; r = d%i; k1 = 0;
    if (r==0) w1[++k1] = d/i;
    while (r)
    {
        r = d%i;
        c = d/i;
        w1[++k1] = c;
        d = i;
        i = r;
    }
    // daca lungimea secventei este un numar par mai adaug un termen de 1
    if (k1%2==0)
        {w1[++k1]=1;w1[k1-1]--;}

    //calculez suma elementelor vectorului fractiei continue
    ok1=0;
    for(i=1;i<=k1;i++)
        ok1+=w1[i];


// fractia a doua...............................................................................
// determin fractia continua atasata cele de-a doua fractii
    d = a2;i = b2; r = d%i; k2 = 0;
    if (r==0) w2[++k2] = d/i;
    while (r)
    {
        r = d%i;
        c = d/i;
        w2[++k2] = c;
        d = i;
        i = r;
    }

    // daca lungimea secventei este un numar par mai adaug un termen de 1
    if (k2%2==0)
        {w2[++k2]=1;w2[k2-1]--;}


    //calculez suma elementelor vectorului fractiei continue
    ok2=0;
    for(i=1;i<=k2;i++)
        ok2+=w2[i];

    // determin secventa comuna celor doi vectori ai fractiilor continue
    i=k1;j=k2;s=0;
    while (i>=1 and j>=1)
    {
        if (w1[i]==w2[j])
                {
                 s=s+2*w1[i];
                 i--;j--;
                }
                else
                 {
                 if (w1[i]<w2[j])   s=s+2*w1[i];
                        else        s=s+2*w2[j];
                  break;
                 }
    }

    // afisez rezultatul
    fout << ok1 + ok2 - s << "\n";
    }

    fin.close();
    fout.close();



    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2456 numinum

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2456 numinum de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2456 numinum