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

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


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

Dornic de o condiţie fizică perfectă, un viitor olimpic naţional la informatică îşi propune să escaladeze cea mai înaltă culme a unui masiv muntos. Se echipează corespunzător, îşi cumpără un termos, îl umple cu apă, culege informaţiile despre traseele existente şi completează astfel fişierul de intrare popas.in. Pe parcursul fiecărui traseu există mai multe izvoare de la care drumeţul îşi poate umple termosul. Ştiind că pe munte este bine să mergi cu pas constant şi fără ruperi de ritm, îşi propune să atingă culmea facând cât mai puţine popasuri (pentru umplerea termosului).

Cerinţă

Dintre toate traseele existente către culme determinaţi-l pe cel pentru care numărul total de popasuri este minim. Dacă sunt mai multe astfel de trasee, se va alege cel care este scris ultimul în fişierul de intrare.

Date de intrare

Fişierul popas.in conţine:
- pe prima linie, k - numărul total de trasee către culme;
- pe fiecare dintre următoarele k linii descrierea câte unui traseu (pe fiecare linie numerele sunt separate prin câte un spaţiu), adică:
- i - numărul asociat traseului (fiecare traseu este identificat în mod unic printr-un număr natural cuprins între 1 şi k);
- r - numărul izvoarelor cu apă rece de pe traseu;
- d1,d2,…,drr numere reprezentând distanţa de la punctul de plecare până la fiecare izvor
- pe ultimele două linii:
- t - distanţa pentru care drumeţului îi este suficientă apa din termos;
- u - distanţa pe care drumeţul o poate străbate fără apă.

Date de ieşire

Fişierul popas.out va conţine pe prima linie, despărţite prin spaţiu, două numere: primul reprezintă numărul minim de popasuri necesare deplasării şi al doilea numărul traseului ales. Dacă problema nu are soluţie fişierul de ieşire va conţine cifra 0.

Restricţii

0<k<=100
0<r<=20
0<di<=360
1<=t<=10
1<=u<=5

În fişierul de intrare toate distanţele sunt exprimate în kilometri
Pentru fiecare traseu distanţa dintre ultimul izvor (cel mai îndepărtat de punctul de plecare) şi culme este de 1 kilometru.
Datele de intrare sunt corecte (nu necesită validare).

Exemple

popas.inpopas.out
3 2 3 12 5 9 1 4 2 9 7 11 3 5 2 16 7 9 8 6 2 1 1
2 1 3 12 5 9 2 3 2 7 11 1 2 0

propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Probleme recomandate
De la OJI 2004: cifre3, concurs3, control, exp1, joc13, lanterna, mosia, perle, reactivi, rj, ron, siruri1, vanatoare
Despre Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, lover, sant1, volei1, ab3, camion1, aranjare, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
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, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, basm, 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
surse trimise | ajutor