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

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


Timp maxim de executie/test:
0.2 secunde
Memorie totala disponibila/stiva:
15 MB/1 MB

Am ajuns cu masina in fata a N stopuri (semafoare). Stopurile sunt unul dupa altul, in linie dreapta, cu o distanta de 10 m intre oricare doua stopuri consecutive.
Fiecare stop are un program de functionare propriu, si anume: stopul i sta Ri secunde pe rosu si Vi secunde pe verde, dupa care revine la culoarea rosie. In momentul de timp 0.5 secunde, toate stopurile incep sa functioneze pe culoarea rosu (fiecare Ri secunde).
Noi ne aflam in fata primului stop (la 10 m de acesta), insa nu plecam imediat ce se face verde. Pentru ca vrem sa facem economie de benzina, asteptam momentul in care daca am pleca am prinde toate stopurile pe verde.
Masina se deplaseaza cu viteza constanta de 10 m/s, accelereaza instantaneu, iar din momentul in care am inceput sa mergem, nu putem opri, incetini sau intoarce. Trebuie sa trecem de toate cele N stopuri.
Putem porni masina doar la timpi multipli de o secunda. Adica numai in momentul 0 secunde, 1 secunda, 2 secunde, ...

Cerinta

Scrieti un program care afla timpul minim la care daca plecam prindem toate stopurile pe verde.

Date de intrare

Pe prima linie a fisierului de intrare stop.in este scris N numarul de stopuri. Pe fiecare dintre urmatoarele N linii sunt scrise cate 2 numere Ri si Vi, separate de un spatiu, reprezentand timpii cat stau rosu si respectiv verde stopurile de la 1 la N.

Date de iesire

Prima linie a fisierului stop.out va contine timpul minim (intreg nenegativ) la care putem pleca astfel incat sa prindem toate stopurile pe verde.

Restrictii

  • 1 <= N <= 1000
  • 0 <= Ri <= 10, pentru orice i de la 1 la N
  • 0 <= Vi <= 10, pentru orice i de la 1 la N
  • 1 <= Ri+Vi <= 10, pentru orice i de la 1 la N
  • Pentru datele de test exista intotdeauna solutie.

Exemplu

stop.in

stop.out

3
1 1
1 2
2 1

3

student Marius Andrei
Facultatea de Automatica si Calculatoare
Contact: marsamg at yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2003: newcomp, rima, algebra, turn1, aparitii, carti1, program1, tgraf, ceas1, spioni, kgb, tabara1, romane, hanoi, lift, pic, sms, fibo, bac, parc, circular, logn, lex, joc7, cuburi1, sant, mobile, pattern, oras, produs, mutare, viteza, concurs2, furnici, homeless, subsir
De acelaşi autor: conflicte, cadere, leaves, na, distanta, ivv, aparitii, tabara1, hanoi, logn, cuburi1, viteza, masina3, anticip, cabane, spp, regine, comoara2, perle, cuvinte1, sortari, triti
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, 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, oak, 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
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, 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, fall, arbsum, conuri, arbvalmax, procente, metrou
Chestionare recomandate
surse trimise | ajutor