| Fişierul intrare/ieşire: | mesaje.in, mesaje.out | Sursă | ONI 2010, clasa a 10-a |
| Autor | Florentina Ungureanu, Mugurel Ionut Andreica | Adăugată de |  Dragos-Alin Rotaru •mathboy |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 6144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mesaje
După multe năzbâtii făcute împreună, Alex şi Cipri nu mai au voie să se întâlnească. Alex – strategul echipei - a plănuit o nouă poznă şi a decis să-i transmită prietenului său planul de luptă, constând din anumite cuvinte dintr-un mesaj m0. Pentru a nu fi descoperiţi, i-a trimis ulterior mai multe mesaje m1, m2, ... lui Cipri, acesta trebuind să le descifreze folosind convenţia secretă stabilită la începutul prieteniei lor şi să „acţioneze”. Fiecare mesaj mi este format din mai multe cuvinte, separate prin câte un spaţiu, numerotate cu valori consecutive, începând de la 1.
Pentru a afla planul, Cipri trebuie să găsească cea mai mare valoare i ≥ 0 astfel încât mesajele mi şi m0 să conţină cel puţin un cuvânt identic având acelaşi număr de ordine în ambele mesaje. Din m0 se păstrează toate cuvintele care se găsesc şi în mesajul mi cu acelaşi număr de ordine ca în m0. Cuvintele păstrate trebuie ordonate în ordine descrescătoare lexicografică a puterii lor. Puterea cuvântului cu numărul de ordine j în m0 este egală cu şirul ordonat descrescător al indicilor mesajelor în care apare cu acelaşi număr de ordine ca în m0. Astfel, un cuvânt care a apărut cu numărul de ordine 2 în mesajele m0, m6 şi m8 are puterea {8, 6, 0}. Dacă două cuvinte au aceeaşi putere, vor rămâne în ordinea din mesajul iniţial. Lui Cipri nu i-a mai rămas decât să citească fiecare cuvânt de la dreapta la stânga şi a descifrat tot planul de luptă!
Cerinţă
Cunoscând mesajele transmise de Alex, ajutaţi-l pe Cipri să descifreze planul de luptă conform convenţiei secrete.
Date de intrare
Fişierul de intrare mesaje.in conţine în ordine mesajele m0, m1, m2, ..., câte unul pe linie.
Date de ieşire
Fişierul de ieşire mesaje.out va conţine pe prima linie numărul n de cuvinte ale planului de luptă, iar pe cea de a doua linie cele n cuvinte ale planului de luptă.
Restricţii si precizări
- Mesajele sunt memorate câte unul pe linie, fiind formate din cuvinte separate prin câte un spaţiu.
- Lungimea unui cuvânt este de maxim 20 de caractere, litere mici ale alfabetului englez.
- Lungimea unui mesaj este de maxim 30002 de caractere.
- Toate mesajele au acelaşi număr de cuvinte.
- Fişierul de intrare conţine cel puţin unul şi cel mult 128 de mesaje.
- Orice linie din fişierul de intrare (mesaj) se termină cu marcajul de sfârşit de linie (newline). Caracterul newline nu va fi considerat ca făcând parte din mesaj.
- Nu există mesaje vide.
- Se acordă 40% din punctajul corespunzător fiecărui test pentru determinarea valorii n şi întregul punctaj pentru rezolvarea corectă a ambelor cerinţe.
Exemplu
| mesaje.in | mesaje.out |
|---|---|
| inosos yy ataeclud ni a yy ataeclud ni yy inosos ni yy inosos bb ataeclud ni acni in e enib | 3 dulceata in sosoni |
| miras ep maeg | 3 sarim pe geam |
Explicaţie
Pentru primul exemplu:
- Mesajele m0 şi m4 nu conţin cuvinte identice cu acelaşi număr de ordine. Mesajele m0 şi m3 conţin trei cuvinte identice cu acelaşi număr de ordine: inosos, ataeclud, ni. În ordinea puterii, ele sunt: ataeclud {3,1,0}, ni {3,1,0}, inosos{3,0}.
Pentru al doilea exemplu :
- Pentru că a primit un singur mesaj, planul de luptă conţine oglinditele cuvintele din textul iniţial având toate aceeaşi putere, citite de la dreapta la stânga.
