.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » oak

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
 .campion
oak


Timp maxim de execuţie/test:
0.5 secunde
Memorie totala disponibilă/stivă:
2 MB/1 MB

La un concurs de maraton participă N broscuţe. Fiind un concurs mai special, fiecare broscuţă are de parcurs propriul traseu, a cărui lungime se cunoaşte şi pe care trebuie să îl parcurgă efectuând cât mai puţine salturi. Pentru a nu fi descalificată, în urma ultimului salt efectuat trebuie să ajungă exact în punctul de finish. Înainte de start fiecărei broscuţe i se comunică două numere naturale distincte reprezentând lungimile salturilor pe care are voie să le execute în timpul maratonului. Cu alte cuvinte, o broscuţă aflată în concurs trebuie să ajungă în punctul de finish al traseului ei, efectuând doar două tipuri de salturi, lungimile acestora fiind impuse de organizator.

Cerinţă

Scrieţi un program care determină pentru fiecare din cele N broscuţe, numărul minim de salturi necesar fiecăreia pentru a atinge punctul de final al traseului repartizat, cunoscând lungimile salturilor pe care le poate efectua.

Date de intrare

Fişierul de intrare oak.in conţine pe prima linie numărul natural N. Următoarele N linii conţin triplete de numere naturale Ai Bi Ti cu semnificaţia broscuţa cu tricoul numărul i va efectua doar salturi de lungimi Ai sau Bi, iar traseul repartizat ei are lungimea Ti. Broscuţele sunt numerotate de la 1 la N, în ordinea din fişierul de intrare.

Date de ieşire

Fişierul de ieşire oak.out va conţine N linii. Pe linia i a fişierului se va scrie numărul minim de salturi necesar broscuţei i pentru a atinge punctul de final al traseului repartizat, sau –1 dacă broscuţa nu va reuşi să-l atingă.

Restricţii

  • 0 < N  < 100 001
  • 0 < Ai < 3 001
  • 0 < Bi < 3 001
  • Ai diferit de Bi
  • 0 < Ti < 1 000 001

Exemple

oak.in oak.out
3
5 6 17
2 4 6
5 6 7
3
2
-1

prof. Dana Lica
Colegiul Naţional "I. L. Caragiale" Ploieşti
danal182001@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, megascoala
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, pipe, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, ozn1, optim, puncte5, swap, tetris3, monede2, ssk
Despre divizibilitate: celule, cai, trei, ruleta, an, factori, perechi, anagrame, axa, perspic, scara, programs, iepuras2, fry, policefm, turist, kfactor, cuc, prime, sqr, evaluare, factk, div3, divizor, euclid, stop, matricea, mutare, viteza, ingerasi, prieteni, robinson, romeo, perechi1, sume1, fact, tzigla, cifru2, elfi, vraji, desen2, exponent, trapez, resturi, exp1, ron, spirala1, gardul, tort, poligon3, sume2, smith, biliard, printesa, secvente1, ultime4, padure, multiplu1, 235, iepurasi, numar3, cmmmc, randomizare, divizori, pitag, bileprime, pin, canguri, numar4, jocprim, covor, nivfractie, cmmdcsecv, ai, grupe2, numerus, sport2, fagure, grad2, sumdivprod, sumprod, paisprezece, numere10, proddiv, puncte4, trifoi, cartier, alune, intersectii, divider, minm, numere11, prodnr, boltz, vistiernic, secvp, extraprime, divizori1, cumpanit, cntgcd, nrdiv, numere12, daruri, imprimanta, puteri, reflex, tg, sprime, diferenta, concurs4, vapoare, inventie, prime2
Chestionare recomandate
surse trimise | ajutor