== include(page="template/taskheader" task_id="mesaj") ==
Poveste și cerință...
!>problema/mesaj?mesaj.jpg!
În țara lui Piticot cuvintele au doar două litere, prima fiind o majusculă (literă mare) iar a doua o minusculă (literă mică). Piticii _Mi_ și _Gi_ se distrează și își trimit mesaje ascunzând cuvintele în cadrul unor secvențe transmise sub forma unor șiruri de litere. Piticul _Mi_ scrie și trimite un mesaj piticului _Gi_ respectând următoarele reguli:
* un mesaj conține una sau mai multe secvențe;
* orice literă care apare în mesaj, de cel puțin două ori, pe poziții alăturate, este numită *terminator*,
* o secvență se încheie când s-a întâlnit o succesiune de litere *terminator*,
* cuvântul este format din prima majusculă și ultima minusculă din secvență, fără a lua în seamă litera *terminator* a secvenței;
* o secvență ascunde un cuvânt dacă *terminatorul* său se repetă de exact două ori și dacă conține cel puțin o literă mare și o literă mică, ignorând *terminatorul* de secvență;
* costul unui cuvânt este egal cu numărul total de apariții al celor două litere din care este format, în cadrul secvenței în care a fost ascuns, luând în considerare inclusiv literele *terminator*.
De exemplu, secvența *s f u E e t R u E E* ascunde un cuvânt deoarece conține și majuscule și minuscule, iar litera terminator de secvență, *E*, se repetă de exact două ori. Secvența ascunde cuvântul *Eu*, iar costul cuvântului este de *5* (3 litere E + 2 litere u).
La primirea mesajului, piticul _Gi_ determină, pentru fiecare majusculă, costul maxim al cuvintelor care încep cu aceasta.
h2. Cerință
Scrieți un program care determină:
# numărul de secvențe trimise care nu ascund cuvinte;
# cuvintele din mesaj, în ordinea în care au fost trimise de piticul _Mi_;
# pentru fiecare majusculă, câte cuvinte care încep cu ea au costul maxim determinat de _Gi_;
h2. Date de intrare
Fișierul de intrare $mesaj.in$ ...
Fișierul de intrare $mesaj.in$ conține pe prima linie un număr natural *P*. Pentru toate testele de intrare, numărul *P* poate avea numai una dintre valorile 1,2 sau 3.
Pe a doua linie a fișierului de intrare se găsește numărul natural *N* reprezentând numărul de litere folosite de _Mi_ pentru scrierea mesajului.
Pe a treia linie se găsesc *N* litere mari și mici ale alfabetului englez, separate prin câte un spațiu, reprezentând literele mesajului, în ordinea în care au fost trimise.
h2. Date de ieșire
În fișierul de ieșire $mesaj.out$ ...
Dacă valoarea lui *P* este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fișierul de ieșire $mesaj.out$ va conține pe prima linie un număr natural reprezentând răspunsul la cerința 1).
Dacă valoarea lui *P* este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fișierul de ieșire $mesaj.out$ va conține cuvintele din mesaj, fiecare cuvânt scris pe câte o linie, în ordinea în care au fost trimise.
Dacă valoarea lui *P* este 3, se va rezolva numai punctul 3) din cerințe. În acest caz, fișierul de ieșire $mesaj.out$ va conține pe fiecare linie câte o majusculă urmată de un număr natural nenul, separate printr-un spațiu. Majusculele vor fi afișate în ordine de la A la Z, însă doar cele patru care au existat în mesaj cuvinte care au început cu ele.
h2. Restricții și precizări
* $1 ≤ *N* ≤ 2000000$
* litera terminator a unei secvențe poate fi ori minusculă ori majusculă;
* ultimele litere din fișier sunt literele *terminator* ale ultimei secvențe din mesajul trimis;
* se garantează că în șirul de litere din fișierul de intrare se află ascuns cel puțin un cuvânt;
* majusculele alfabetului englez sunt *A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z*;
* pentru 50% din teste *N* ≤ 1000000;
* Pentru rezolvarea cerinței 1) se acordă 20 de puncte, pentru rezolvarea cerinței 2) se acordă 40 de puncte, iar pentru rezolvarea cerinței 3) se acordă 40 de puncte.
h2. Exemplu 1
table(example){width: auto;}.
|_. mesaj.in |_. mesaj.out |
| 1
34
w w w w e D o r F D o r r t R n e R e y y j j i M o e i t t t j w w
| 4
|
h3. Explicație
h2. Restricții
table{width: auto;}.
|^. Textul conține șase secvențe:
# w w w w
# e D o r F D o r r
# t R n e R e y y
# j j
# i M o e i t t t
# j w w
|^. Sunt 4 secvențe care nu ascund cuvinte:
# prima secvență și a patra deoarece conțin numai terminatorul;
# secvența a cincea nu se decodifică deoarece terminatorul se repetă de mai mult de două ori;
# secvența a șasea nu conține majuscule;
|
h2. Exemplu 2
table(example){width: auto;}.
|_. mesaj.in |_. mesaj.out |
| 2
34
u N a a e D o r F D o r r t R n e R e y y j j i M o e i t t t j w w
| Nu
Do
Re
|
h3. Explicație
* $... ≤ ... ≤ ...$
table{width: auto;}.
|^. Textul conține șase secvențe:
# u N a a
# e D o r F D o r r
# t R n e R e y y
# j j
# i M o e i t t t
# j w w
|^. Prima secvență are terminatorul *a* care se repetă de două ori și ascunde cuvântul *Nu*.
A doua secvență are terminatorul *r* și ascunde cuvântul *Do*.
A treia are terminatorul *y* și ascunde cuvântul *Re*.
Ultimele trei secvențe nu ascund cuvinte.
|
h2. Exemplu
h2. Exemplu 3
table(example).
table(example){width: auto;}.
|_. mesaj.in |_. mesaj.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
24
A a t t B b B t t e A e a n n B w I I F i e F F
|A 2
B 1
F 1
|
h3. Explicație
...
table{width: auto;}.
|^. Textul conține cinci secvențe:
# A a t t
# B b B t t
# e A e a n n
# B w I I
# F i e F F
|^. Cuvintele transmise în mesaj sunt:
1. *Aa* (cost *2*)
2. *Bb* (cost *2*)
3. *Aa* (cost *2*)
4. *Bw* (cost *2*)
5. *Fe* (cost *4*)
Costul maxim al cuvintelor care încep cu *A* este *2* și au fost *2* cuvinte transmise.
Pentru litera *B* s-a transmis un singur cuvânt de cost maxim *3*.
Pentru litera *F* s-a transmis un singur cuvânt de cost maxim *4*.
|
== include(page="template/taskfooter" task_id="mesaj") ==
