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.