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