Fişierul intrare/ieşire:mesaje.in, mesaje.outSursăONI 2010, clasa a 10-a
AutorFlorentina Ungureanu, Mugurel Ionut AndreicaAdăugată demathboyDragos-Alin Rotaru mathboy
Timp execuţie pe test0.05 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/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.inmesaje.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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content