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

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


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

Scufiţa Roşie vrea din nou să ajungă la bunicuţa şi pentru asta trebuie să traverseze pădurea fermecată. Pe harta pădurii fermecate, casa Scufiţei Roşii se află în punctul de coordonate (0, 0), iar casa bunicii în punctul de coordonate (x, y).
Scufiţa Roşie iese din casă la momentul de timp 0 şi se deplasează cu viteză constantă de 1 m/s.
În pădurea fermecată apar, la anumite momente de timp, ziduri peste care Scufiţa Roşie nu poate trece. Dacă totuşi în momentul în care zidul apare Scufiţa Roşie se află chiar în poziţia în care apare zidul, ea va reuşi să treacă dincolo de zid. Zidurile sunt drepte paralele cu axa Ox. Pentru fiecare zid i (i=1, 2, ..., n; unde n reprezintă numărul de ziduri) cunoaştem momentul de timp ti la care zidul apare, precum şi poziţia sa pi (mai exact, zidul va fi o dreaptă cu ecuaţia y=pi).

Cerinţă

Să se determine timpul minim în care Scufiţa Roşie poate ajunge la casa bunicii (dacă este posibil).

Date de intrare

Fişierul de intrare basm.in conţine pe prima linie două numere naturale separate prin spaţiu reprezentând coordonatele x y ale casei bunicii. Pe cea de a doua linie se află numărul natural n, reprezentând numărul de ziduri. Pe următoarele n linii sunt descrise cele n ziduri, câte un zid pe o linie, sub forma a două numere întregi separate prin spaţiu pi ti.

Date de ieşire

Fişierul de ieşire basm.out va conţine o singură linie pe care va fi scrisă valoarea -1 (dacă Scufiţa Roşie nu poate ajunge la casa bunicii). În caz contrar, pe prima linie se va scrie un număr real cu cel puţin 6 zecimale, reprezentând timpul minim în care Scufiţa Roşie ajunge la casa bunicii.

Restricţii

  • 1 <= x, y, ti <= 109
  • 0 <= n <= 100 000
  • 1 <= pi < y
  • Nu există două ziduri în aceeaşi poziţie.
  • Rezultatul afişat va fi considerat corect dacă diferenţa absolută dintre rezultatul corect şi cel afişat este <0.0001.

Exemple

basm.in basm.out basm.in basm.out
7 7
1
4 5
10.00000000 7 7
1
4 3
-1

prof. Emanuela Cerchez
Liceul de Informatică „Grigore Moisil” Iaşi
emanuela.cerchez@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2009: efort, muzeu, bal, seti, dansatori, smith, timer, secvsir, vot, cetati, reziduu, biliard, prefix1, accesibil, dp, jocv, placa, palc, prod3, predecesor, standard, cantor, nkbiti, nori, triti, kperms, sotron1, impozit, tablite, fazan, lanturi, secvpar, tom, joker, matriosca, asociativ, lego, medalii, permutari, cfr, treegame, scanduri, site, fotbal, links, kbiti, segm, album, iepurasi, jucarii, m4, bradut, trmv, colorare, greutati, concat, graphgame, ic, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre stiva: sl, teren, reactii, complex, auto, bile3, chimie2, vile, puncte1, masina3, matrice1, dir, stiva, munte2, perle, predecesor, expresie1, telecab, expresie2, liste, intervale, jocs, expeval, copaci2, plus, azeval, unific, swap, stiva1, ecp, charlie
Despre geometrie: forum, supertri, ozn, detinut, atac, afise, mere, ff, teren, volei, aven, patrate, robot, pahare, pendul, robot2, dragon, poligon, druid, laser, patrate3, ploaia, donald, lot, atac1, arcas, paralel, dotnet, aedaro, vectori, spirala, distanta, triunghi, center, harta1, seceta, antena, poligon1, benzina, zoo, texan, oypara, dreptc, mosia, sea, poligon3, poligon2, snipers, cetati, placa, nori, cerc, smin, cern, cuiburi, acerc, select, proiect, poligon4, terenuri, monoton, acoperire, capra, testament, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, turist, bacan, toys, scor2, chimie2, politics, submat, scoici, ham, jokes, trecere, multiplu, paralel, tvshow, sirag1, tabara, munte, sport, puncte1, sume1, schi, granita, tren3, sant1, volei1, poze, maroco, dreptc, dist1, tir1, control, mosia, popas, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, vot, balcon, joc14, cerc, k1, segm, calorii, ordonare, greutati, arctir, macheta, poligon4, centrala, robot4, lcdr, maxviz, sdmin, qtri, arme, flori1, parc1, mijloc, bile6, proiecte, patru, drept2, subsecvente, cursa1, eoliene, vintage, dreapta, riglef, rebus1, rascoala, zimeria, praslea, aperm, unudoi, gropi1, piscina, restaurare, cabana, culori3
Software recomandat
surse trimise | ajutor