Î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 5 (3 litere E + 2 două litere u).
La primirea mesajului, piticul Gi determină, pentru fiecare majusculă, costul maxim al cuvintelor care încep cu aceasta.
Cerinţe
Scrieţi un program care determină:
1) numărul de secvențe trimise care nu ascund cuvinte;
2) cuvintele din mesaj, în ordinea în care au fost trimise de piticul Mi;
3) pentru fiecare majusculă, câte cuvinte care încep cu ea au costul maxim determinat de Gi.
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. 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.
Date de ieșire
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 pentru care au existat în mesaj cuvinte care au început cu ele.
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.
Exemplul 1
mesaj.in
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
mesaj.out
4
Explicație
Textul conține șase secvențe:
w w w we D o r F D o r rt R n e R e y yj ji M o e i t t tj 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.
Exemplul 2
mesaj.in
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
mesaj.out
Nu Do Re
Explicație
Textul conține șase secvențe:
u N a ae D o r F D o r rt R n e R e y yj ji M o e i t t tj 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.
Exemplul 3
mesaj.in
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
mesaj.out
A 2 B 1 F 1
Explicație
Textul conține cinci secvențe:
A a t tB b B t te A e a n nB w I IF i e F F
Cuvintele transmise în mesaj sunt
Aa(cost2)Bb(cost3)Aa(cost2)Bw(cost2)Fe(cost4)
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.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Mesaj:
#include <fstream>
#include <cctype>
using namespace std;
ifstream in("mesaj.in");
ofstream out("mesaj.out");
int majCounts[256];
int minCounts[256];
int maxCost[256];
int maxCostCounts[256];
int main() {
int P;
in >> P;
int N;
in >> N;
int numSecvente = 0;
int numSecventeCuCuvinte = 0;
char ch = '#';
int countCh = 1;
char majCh = '#';
char minCh = '#';
for (int i = 0; i <= N; ++ i) {
char peekCh;
if (i < N) {
in >> peekCh;
} else {
peekCh = '#';
}
if (ch == peekCh) {
countCh ++;
} else {
switch (countCh) {
case 1:
switch (P) {
case 1:
if (isupper(ch) && majCh == '#') majCh = ch;
if (islower(ch)) minCh = ch;
break;
case 2:
if (isupper(ch) && majCh == '#') majCh = ch;
if (islower(ch)) minCh = ch;
break;
case 3:
if (isupper(ch) && majCh == '#') majCh = ch;
if (islower(ch)) minCh = ch;
if (isupper(ch)) majCounts[ch] ++;
if (islower(ch)) minCounts[ch] ++;
break;
}
break;
case 2:
switch(P) {
case 1:
numSecvente ++;
if (majCh != '#' && minCh != '#') numSecventeCuCuvinte ++;
majCh = minCh = '#';
break;
case 2:
if (majCh != '#' && minCh != '#') {
out << majCh << minCh << '\n';
}
majCh = minCh = '#';
break;
case 3:
if (isupper(ch)) majCounts[ch] += 2;
if (islower(ch)) minCounts[ch] += 2;
if (majCh != '#' && minCh != '#') {
int cost = majCounts[majCh] + minCounts[minCh];
if (cost > maxCost[majCh]) {
maxCost[majCh] = cost;
maxCostCounts[majCh] = 1;
} else if (cost == maxCost[majCh]) {
maxCostCounts[majCh] ++;
}
}
majCh = minCh = '#';
for(int ii=0; ii<256;ii++) majCounts[ii]=0;
for(int ii=0; ii<256;ii++) minCounts[ii]=0;
break;
}
break;
default:
switch (P) {
case 1:
numSecvente ++;
majCh = minCh = '#';
break;
case 2:
majCh = minCh = '#';
break;
case 3:
majCh = minCh = '#';
for(int ii=0; ii<256;ii++) majCounts[ii]=0;
for(int ii=0; ii<256;ii++) minCounts[ii]=0;
break;
}
}
countCh = 1;
ch = peekCh;
}
}
switch(P) {
case 1:
out << numSecvente - numSecventeCuCuvinte << '\n';
break;
case 3:
for (char ch = 'A'; ch != 'Z'; ++ ch) {
if (maxCost[ch]) {
out << ch << ' ' << maxCostCounts[ch] << '\n';
}
}
break;
}
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1215 Mesaj
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1215 Mesaj de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!