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

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


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

N pitici (numerotaţi de la 1 la N) au căzut într-o groapă adâncă de D cm. Fiecare pitic îşi cunoaşte înălţimea umerilor (adică distanţa de la pământ la umerii săi), precum şi lungimea braţelor. Prin urmare, dacă piticul i (1≤i≤N) are înălţimea umerilor Hi cm şi lungimea braţelor Li cm, atunci când el va sta în picioare cu braţele în sus va atinge înălţimea Hi+Li cm.
Piticii se pot urca unii pe umerii celorlalţi formând astfel un singur turn. Dacă piticul i stă cu mânile întinse şi este urcat pe umerii piticului jk, care stă pe umerii lui jk-1, ... care stă pe umerii lui j1 atunci el va atinge înălţimea Hj1+Hj2 +…+Hjk+Hi+Li.
Dacă un pitic atinge marginea gropii (adică Hj1 + Hj2 +… + Hjk+Hi+Li ≥ D), el poate ieşi din groapă.

Cerinţă

Să se determine numărul maxim de pitici care pot ieşi din groapă.

Date de intrare

Fişierul de intrare pitici.in conţine pe prima linie numărul natural N reprezentând numărul de pitici. Pe următoarele N linii sunt descrişi piticii. Mai exact, pe linia i+1 se află două numere naturale separate prin spaţiu Hi şi Li reprezentând înălţimea umerilor şi respectiv lungimea braţelor piticului i (1≤i≤N). Pe ultima linie este scris un număr natural D reprezentând adâncimea gropii.

Date de ieşire

Fişierul de ieşire pitici.out va conţine o singură linie pe care va fi scris numărul natural X reprezentând numărul maxim de pitici care pot ieşi din groapă.

Restricţii

1 ≤ N ≤ 2000
1 ≤ Hi ≤ 105 (1 ≤ i ≤ N)
1 ≤ Li ≤ 105 (1 ≤ i ≤ N)
1 ≤ D ≤ 105

Piticii care ies nu mai intră înapoi.
Pentru 70% din teste N ≤ 100; D, Hi, Li ≤ 1000.

Exemple

pitici.inpitici.outExplicaţii
7 2 4 3 2 4 1 7 5 2 1 6 4 6 1 30 3 De exemplu, pot ieşi piticii 1 5 6

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot IS 2008: arbnr, center, sirag1, cod1, tabara, desen1, munte, pipe, euclid, sport, stive, bombe, shgraf, paintball, arb, pav
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, 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, basm, 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 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, 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, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, bombe, pic, bac, pal, antena, culmi, numar2, lover, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
Software recomandat
surse trimise | ajutor