farey

Secventa Farey

== include(page="template/taskheader" task_id="farey") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| farey.in | farey.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="farey") ==

==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
 
 
 
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")==