Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | farey.in, farey.out | Sursă | BOI 2003 |
| Autor | Mihai Patrascu | Adăugată de | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Secventa Farey
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
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.
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.
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.
Restrictii si precizari
Ÿ 1 < N <= 40 000
Ÿ 40% din teste vor avea K <= 50 000
Ÿ toate datele de test folosite pentru evaluare vor avea N >= 10 000
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
