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

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


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

Considerăm un joc bazat pe un dispozitiv ca în imaginea de mai jos:



Dispozitivul constă dintr-o mulţime de platforme orizontale de diferite lungimi, plasate la diferite înălţimi. Platforma cea mai joasă este podeaua (este plasată la înălţimea 0 şi are lungime infinită).
Dintr-o poziţie specificată, este lăsată să cadă o minge, la momentul 0. Mingea cade cu viteză constantă de 1 metru pe secundă. Când mingea ajunge pe o platformă, începe să se rostogolească spre unul din capetele acesteia, la alegerea jucătorului, cu aceeaşi viteză de 1 metru pe secundă. Când mingea ajunge la capătul platformei, îşi continuă căderea liberă, pe verticală. Mingea nu are voie să cadă liber mai mult de MAX metri odată (între două platforme).

Cerinţă

Scrieţi un program care determină un mod de rostogolire a mingii pe platforme astfel încât să ajungă la podea cât mai repede posibil.

Date de intrare

Fişierul de intrare fall.in conţine pe prima linie numerele naturale N X Y MAX, separate prin câte un spaţiu, reprezentând numărul de platforme (excluzând podeaua), poziţia de plecare a mingii (abscisa şi ordonata), şi respectiv distanţa maximă pe care mingea are voie să cadă; platformele sunt numerotate de la 1 la N. Fiecare dintre următoarele N linii conţine trei numere întregi X1 X2 H, separate prin spaţii; numerele de pe cea de a i-a linie dintre cele N semnifică faptul că platforma i este situată la înălţimea H, între coordonatele orizontale X1 şi X2 inclusiv (X1<X2, i=1..N).

Date de ieşire

Fişierul de ieşire fall.out va conţine o singură linie pe care va fi scris un număr întreg T, reprezentând timpul minim în care mingea atinge podeaua.

Restricţii

1≤N≤1000
-20000≤X1, X2≤20000, pentru 1≤i≤N
0<H<Y≤20000
• Diametrul mingii şi grosimea platformelor se ignoră. Dacă mingea cade exact pe marginea unei platforme, se consideră că a căzut pe platformă.
• Oricare două platforme nu au puncte comune.
• Pentru datele de test există întotdeauna soluţie.
• Toate dimensiunile sunt exprimate în metri.

Exemple

fall.infall.out
3 8 17 20 0 10 8 0 10 13 4 14 3 23

propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la CEOI 2000: omida
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor