Diferențe pentru problema/mesaj între reviziile #11 si #35

== include(page="template/taskheader" task_id="mesaj") ==

Î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:

!>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$],

* 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.

* 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*;

# 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$ 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.

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

* $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;

* 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;

* 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

h2. Exemplu 1

table(example).
|_.  |_.  |

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
|

h2. Explicații

h3. Explicație
 
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).

table(example){width: auto;}.

|_. mesaj.in |_. mesaj.out |

|Textul conține șase secvențe:
1) w w w w
2) e D o r F D o r r
3) t R n e R e y y
4) j j
5) i M o e i t t t
6) 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;

| 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 3
 
table(example){width: auto;}.
|_. mesaj.in |_. mesaj.out |
| 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") ==