Problema OLI 2012

[•S7012MY]

Am primit problema asta la oli si nimeni n-a rezolvat-o in concurs si probabil n-o sa fie solutii oficiale. Imi poate spune cineva cum se rezolva ?

PROBLEMA 2 – Fracţie

   Algorel a învăţat la matematică despre mulţimea numerelor naturale şi mulţimea numerelor raţionale. El poate să numere foarte uşor de la 1 la n în mulţimea numerelor naturale şi ar dori să numere la fel de simplu şi în mulţimea numerelor raţionale. Pentru un număr natural dat n, el scrie toate fracţiile ireductibile subunitare cu numitorul cel mult egal cu n în ordine crescătoare (şirul începe cu 0=0/1 şi se termină cu 1=1/1).
De exemplu, pentru n=5 obţine şirul de fracţii: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.
   Ajutaţi-l pe Algorel şi scrieţi un program care pentru un număr n şi o fracţie a/b date returnează fracţia scrisă după aceasta în şirul ordonat crescător al fracţiilor ireductibile cu numitorul mai mic sau egal cu n.

Date de intrare
   Fişierul de intrare fractie.in conţine pe prima linie, separate prin câte un spaţiu,  numerele naturale n, a şi b, n reprezentând numitorul maxim al fracţiilor din şir, iar a şi b numărătorul şi numitorul fracţiei date.

Date de ieşire
      Fişierul de ieşire fractie.out va conţine pe unica sa linie două numere separate printr-un spaţiu, reprezentând prima fracţie mai mare decât a/b din şirul ordonat crescător al fracţiilor ireductibile cu numitorul mai mic sau egal decât n.

Restricţii şi precizări
1 ≤ a < b ≤ n ≤ 1 000 000 000

Exemplu

fractie.in   fractie.out
5 2 3            3 4
Explicaţie
pentru n=5 se obţine şirul de fracţii: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1, iar răspunsul este 3/4

Timp maxim de execuţie/test : 1 secundă

[•mathboy]

Mi se pare asemanatoare cu o problema data la BOI in 2003.

[•S7012MY]

Nu, problemele nu sunt asemanatoare deoarece in problema de la BOI tu trebuie sa calculezi indicatorul lui euler si tu nu-l poti calcula pt n=1 000 000 000 si sa intre in timp.

Oricum din moment ce problema a fost data la OLI ar trebui sa existe o solutie simpla.

[•klamathix]

The really cool property of irreducible fractions is that if a/b and c/d are consecutive in some Farey sequence, then the "mediant" (a+b)/(c+d) is the first fraction that appears between them in a higher-order sequence. For example, the first fraction to appear between 1/2 and 2/3 will be 3/5.

http://infoweekly.blogspot.com/2007/10/rational-search.html

Scoti o solutie din citatul ala de mai sus.

Daca asta e si solutia autorilor sunt cam evil.Greu de scos chestia asta daca nu esti familiar cu tematica.
Adica se vede ca daca a / b si c / d sunt fractii consecutive atunci ad - bc = 1. Dar nu mi-ar fi trecut prin cap sa o scriu pentru 3 fractii consecutive si sa-mi dea chestia aia
Da nu-i vorba, si in Suceava se dadea cuplaj la OLI mai demult fara nicio problema  

[•Cosmin]

la secventa ii zice farey sequence, am vazut problema la usaco prin 98 ...

pardon, la usaco era sa scoti toata secventa in ordine si se facea asa ceva:

Cod:

rec(a, b, c, d):
  if b + d > n
     return
  rec(a, b, a + c, b + d)
  print((a + c) / (b + d))
  rec(a + c, b + d, c, d)

rec(0, 1, 1, 1)

dar cred ca se poate adapta sa rezolve si problema voastra.

parca in arta programarii calculatoarelor sunt cateva problemute cu secvente farey, dar nu mi se pare ca inveti prea multe din o problema ca asta.

am gasit problema http://www.uwp.edu/sws/usaco/1999/Fall/a-prob.htm

Aveti aici nationalele americanilor http://www.uwp.edu/sws/usaco unele au si explicatii de solutii

[•S7012MY]

Multumesc mult pt link-uri.

OFF: olimpicii americani sunt chinezi ?

[•klamathix]

Ei, si tu repede cu generalizarile.
Mai sunt si indieni.