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

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


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Textul unei carti este constituit din N linii, numerotate de la 1 la N.
Într-o linie pot exista una sau mai multe referinte la note de subsol. O nota de subsol este constituita din una sau mai multe linii si trebuie sa apara obligatoriu pe aceeasi pagina cu linia care contine referinta la nota de subsol respectiva. Notele de subsol sunt scrise in partea de jos a paginii, iar dupa o nota de subsol poate sa urmeze pe aceeasi pagina doar o alta nota de subsol.
Se cunoaste numarul maxim de linii care pot fi scrise pe aceeasi pagina (linii de text si liniile notelor de subsol).

Cerinta

Scrieti un program care sa determine numarul minim de pagini pe care le poate avea cartea.

Date de intrare

Fisierul de intrare carte.in contine pe prima linie doua numere naturale N si K, separate printr-un spatiu (N reprezinta numarul de linii din carte, iar K reprezinta numarul maxim de linii ce pot fi scrise pe o pagina). Pe cea de a doua linie este scris un numar natural F care reprezinta numarul de note de subsol din carte. Fiecare dintre urmatoarele F linii contine câte doua numere naturale X Y separate printr-un spatiu, cu semnificatia ca pe cea de a X-a linie de text din carte apare o referinta la o nota de subsol formata din Y linii. Notele de subsol sunt specificate în ordinea liniilor în care ele sunt referite.

Date de iesire

Fisierul de iesire carte.out va contine o singura linie pe care va fi scris numarul minim de pagini din care este constituita cartea.

Restrictii si precizari

  • 2 <= N <= 1000
  • 1 <= K <= 200
  • 1 <= F <= 100
  • Pentru datele de test exista întotdeauna solutie.

Exemplu

carte.in carte.out carte.in carte.out carte.in carte.out
5 5
1
3 2

2

7 3
2
2 1
4 2
4 10 5
5
3 3
4 1
6 2
6 1
9 3

6

Explicatii (o solutie pentru a obtine numarul minim de pagini specificat în fiecare exemplu):
În primul exemplu pe prima pagina sunt scrise liniile de text 1, 2, 3 si nota de subsol referita în linia 3, iar pe a doua pagina sunt scrise liniile de text 4 si 5.
În cel de al doilea exemplu, pe prima pagina sunt scrise liniile de text 1 si 2, precum si nota de subsol referita în linia 2. Pe cea de a doua pagina este scrisa linia 3, pe cea de a treia pagina este scrisa linia 4 si nota de subsol referita în linia 4, iar pe a patra pagina sunt scrise liniile 5, 6, 7.
În cel de al treilea exemplu, pe pagina 1 sunt scrise liniile de text 1 si 2. Pe a doua pagina sunt scrise linia de text 3 si nota de subsol referita în linia 3. Pe a treia pagina sunt scrise liniile 4 si 5, precum si nota de subsol referita în linia 4. Pe pagina a patra sunt scrise liniile 6 si 7, precum si cele doua note de subsol scrise referite în linia 6. Pe pagina a cincea sunt scrise liniile 8 si 9, precum si nota de subsol referita în linia 9. Iar pe pagina a sasea este scrisa linia 10.

prof. Marinel Serban
Liceul de Informatica "Grigore Moisil" Iasi
Contact:marinel_serban@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, pajura, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, cutie2, loc, depou, nr3, zid, felinare, sir3, sqr, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, munte1, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, sant1, imagine, ocr, perfect, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, dansatori, smith, tom, matriosca, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, stelar, joct, minmax, cladire, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
Despre Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, exam, subperm, piloti, barca1, pitici, 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
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, 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, popas, 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
surse trimise | ajutor