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

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

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

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

h2. Exemplu

table(example){width: auto;}.

table(example).

|_. mesaj.in |_. mesaj.out |
| 1
34

| 4
|

h3. Explicație

h2. 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;

table(example).
|_. Textul conține șase secvențe: |_. Sunt 4 secvențe care nu ascund cuvinte: |
|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
|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

h2. Exemplu

table(example){width: auto;}.

table(example).

|_. mesaj.in |_. mesaj.out |
| 2
34

Re
|

h3. Explicație

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

table(example).
|_. Textul conține șase secvențe: |_.
|
|1) u N a a
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
|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

h2. Exemplu

table(example){width: auto;}.

table(example).

|_. mesaj.in |_. mesaj.out |
| 3
24

F 1
|

h3. Explicație

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

table(example).
|_. Textul conține cinci secvențe: |_. Cuvintele transmise în mesaj sunt |
|1) A a t t
2) B b B t t
3) e A e a n n
4) B w I I
5) F i e F F
|Aa (cost 2)
Bb (cost 2)
Aa (cost 2)
Bw (cost 2)
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") ==