Un editor de texte evoluat trebuie
sa includa facilitatea de indexare a documentelor.
Un document
este constituit dintr-o succesiune de paragrafe. Un paragraf
este constituit din una sau mai multe linii. Paragrafele sunt separate prin
exact o linie goala.
În primul rând documentul
este paginat, fiecare pagina fiind constituita din maxim n linii. Liniile sunt plasate în pagina în ordinea în care apar în document, pâna
când pagina "se umple" (contine n linii), respectând în acelasi timp si urmatoarele reguli de formatare:
1. Daca ultima linie a unei pagini este ultima linie a unui paragraf, atunci
urmatoarea linie goala este eliminata (adica pagina urmatoare nu va începe cu
linie goala, ci cu prima linie din paragraful urmator).
2. Daca ultima linie a unei pagini este prima linie a unui paragraf care contine
mai mult de o linie (aceasta linie este denumita în tehnoredactare linie orphan),
atunci aceasta linie este mutata pe pagina urmatoare.
3. Daca ultima linie a unei pagini este penultima linie a unui paragraf care
contine mai mult de 3 linii, atunci aceasta linie este mutata pe ultima linie
(în caz contrar ultima linie a paragrafului ar fi prima linie de pe pagina urmatoare,
ceea ce în tehnoredactare este denumita linie widow).
4. Daca ultima linie de pe pagina este penultima linie a unui paragraf care
contine doua sau trei linii, atunci întregul paragraf este mutat pe pagina urmatoar
(evitând în acest fel sa obtinem atât linie orphan cât si linie widow)
.
Regulile de paginare sunt aplicate în ordine, de la începutul documentului,
pagina cu pagina.
Consideram cuvânt
o succesiune de litere din alfabetul englez (nu se va face distinctie între
literele mici si literele mari).
Un index
este lista strict ordonata lexicografic a tuturor cuvintelor care apar în document
si a numerelor de pagina la care apar aceste cuvinte. Numerele de pagina la
care apare fiecare cuvânt trebuie sa fie specificate în ordine crescatoare,
si vor fi separate prin virgula. Daca un cuvânt apare pe trei sau mai multe
pagini consecutive, atunci se specifica doar numarul primei pagini si numarul
ultimei pagini dintre acestea, separate prin liniuta (caracterul '-').
De exemplu: MUSEUM 3-5,7-10,12,18,22-29
Cerinţă
Date fiind numarul de linii din pagina si documentul să se determine indexul.
Date de intrare
Fişierul de intrare index.in conţine pe prima linie un număr natural nenul n, reprezentând numarul maxim
de linii care pot fi plasate într-o pagina. Pe urmatoarele linii este scris
documentul care trebuie sa fie indexat.
Date de ieşire
Fişierul de ieşire index.out va conţine mai multe linii, câte una pentru fiecare cuvânt din document.
Fiecare linie va contine un cuvânt urmat de un singur spatiu si apoi de lista
numerelor de pagina la care apare cuvântul, formatata ca în enunt. Cuvintele
vor fi specificate în ordine strict lexicografica si vor fi scrise cu majuscule.
Restricţii şi precizări 4<=n<=100
Dimensiunea documentului care trebuie sa fie indexat nu depaseste 20
000 bytes.
Liniile din document nu încep si nici nu se termina cu spatii.
Documentul nu va contine doua linii goale consecutive.
Prima linie a documentului nu este goala.
Lungimea unei linii nu depaseste 200
de caractere.
Exemplu
index.in
index.out
5
Din anul 2002 mii de elevi participa
la programul de pregatire de performanta in informatica .campion.
In fiecare an cel putin 10 elevi de la fiecare grupa participa
la finala .campion
cei mai buni se intrec cu cei
mai buni
.campion se adreseaza tuturor
celor pentru care performanta
reprezinta o pasiune, celor pentru
care rezolvarea
unei probleme este o bucurie
celor impatimiti de jocurile
mintii
an de an cei care au fost elevi
devin profesori
se alatura echipei .campion
pentru a insufla mai departe pasiunea pentru performanta in informatica
celor ce le calca pe urme
celor ce urmeaza sa fie cel putin
la fel de buni
pe cat au fost si ei
.campion e super!
participa si tu la .campion!
alatura-te celor mai buni!
A
4
ADRESEAZA 2
ALATURA 4,6
AN 1,4
ANUL 1
AU 4,5
BUCURIE 3
BUNI 2,5,6
CALCA 4
CAMPION 1,2,4,6
CARE 2-4
CAT 5
CE 4,5
CEI 2,4
CEL 1,5
CELOR 2-6
CU 2
DE 1,3-5
DEPARTE 4
DEVIN 4
DIN 1
E 6
ECHIPEI 4
EI 5
ELEVI 1,4
ESTE 3
FEL 5
FIE 5
FIECARE 1
FINALA 1
FOST 4,5
GRUPA 1
IMPATIMITI 3
IN 1,4
INFORMATICA 1,4
INSUFLA 4
INTREC 2
JOCURILE 3
LA 1,5,6
LE 4
MAI 2,4,6
MII 1
MINTII 3
O 3
PARTICIPA 1,6
PASIUNE 3
PASIUNEA 4
PE 4,5
PENTRU 2-4
PERFORMANTA 1,2,4
PREGATIRE 1
PROBLEME 3
PROFESORI 4
PROGRAMUL 1
PUTIN 1,5
REPREZINTA 3
REZOLVAREA 3
SA 5
SE 2,4
SI 5,6
SUPER 6
TE 6
TU 6
TUTUROR 2
UNEI 3
URME 4
URMEAZA 5