==Include(page="template/taskheader" task_id="farey")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
Secventa Farey
 
 
 
O secventa farey de ordinul N este secventa tuturor fractiilor ireductibile ^p/[q] cu 0 < p < q <= N, aranjate in ordine crescatoare. De exemplu, secventa Farey de ordinul 5 este:
 
 
 
^1/[5 ] ^1/[4 ] ^1/[3 ] ^2/[5 ] ^1/[2 ] ^3/[5 ] ^2/[3 ] ^3/[4 ] ^4/[5
 
 
 
]Vom numerota fractiile din secventa incepand cu 1. De exemplu, a 6-a fractie din secventa Farey de ordin 5 este ^3/[5.
 
 
 
]Cerinta
 
Dandu-se N si un numar K, aflati a K-ua fractie dintr-o secventa Farey de ordin N.
 
h2. Date de Intrare
 
Fisierul de intrare farey.in contine o singura linie cu numerele N si K separate prin spatiu. K va fi mereu un index valid, adica va fi cel putin 1 si nu va fi mai mare decat numarul de fractii din secventa Farey de ordin N.
 
h2. Date de Iesire
 
Fisierul de iesire farey.out va contine o singura linie cu doua numere intregi P si Q separate prin spatiu. Fractia ^P/[Q] trebuie sa fie a K-ua fractie din secventa Farey de ordin N. Fractia trebuie sa fie ireductibila, adica cel mai mare divizor comun dintre P si Q trebuie sa fie 1.
 
h2. Restrictii si precizari
 
&#159; 1 < N <= 40 000
 
&#159; 40% din teste vor avea K <= 50 000
 
&#159; toate datele de test folosite pentru evaluare vor avea N >= 10 000
 
h2. Exemplu
 
farey.in farey.out
5 6 3 5
 
 

==Include(page="template/taskheader" task_id="farey")==
 
O secventa farey de ordinul $N$ este secventa tuturor fractiilor ireductibile $^P^/{~Q~}$ cu $0 < P < Q &le; N$, aranjate in ordine crescatoare. De exemplu, secventa Farey de ordinul 5 este:
 
p=. $^1^/{~5~} ^1^/{~4~} ^1^/{~3~} ^2^/{~5~} ^1^/{~2~} ^3^/{~5~} ^2^/{~3~} ^3^/{~4~} ^4^/{~5~}$
 
Vom numerota fractiile din secventa incepand cu $1$. De exemplu, a $6$-a fractie din secventa Farey de ordin $5$ este $^3^/{~5~}$.
 
h2. Cerinta
 
Dandu-se $N$ si un numar $K$, aflati a $K$-ua fractie dintr-o secventa Farey de ordin $N$.
 
h2. Date de Intrare
 
Fisierul de intrare $farey.in$ contine o singura linie cu numerele $N$ si $K$ separate prin spatiu. $K$ va fi mereu un index valid, adica va fi cel putin $1$ si nu va fi mai mare decat numarul de fractii din secventa Farey de ordin $N$.
 
h2. Date de Iesire
 
Fisierul de iesire $farey.out$ va contine o singura linie cu doua numere intregi $P$ si $Q$ separate prin spatiu. Fractia $^P^/{~Q~}$ trebuie sa fie a $K$-ua fractie din secventa Farey de ordin $N$. Fractia trebuie sa fie ireductibila, adica cel mai mare divizor comun dintre $P$ si $Q$ trebuie sa fie $1$.
 
h2. Restrictii si precizari
 
* $1 < N &le; 40 000$
* $40%$ din teste vor avea $K &le; 50 000$
* toate datele de test folosite pentru evaluare vor avea $N &ge; 10 000$
 
h2. Exemplu
 
table(example). |_. farey.in |_. farey.out |
| 5 6 | 3 5 |
 
h3. Sfat prietenesc
 
Aceasta nu este o problema de matematica; pentru a o rezolva sunt necesare doar cunostiinte matematice elementare. Trebuie in schimb sa gasiti un algoritm performant pentru a o rezolva.
 
==Include(page="template/taskfooter" task_id="farey")==

Sfat prietenesc: aceasta nu este o problema de matematica; pentru a o rezolva sunt necesare doar cunostiinte matematice elementare. Trebuie in schimb sa gasiti un algoritm performant pentru a o rezolva.
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/farey/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="farey")==

895