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 m[0]. Pentru a nu fi descoperiți, i-a trimis ulterior mai multe mesaje m[1], m[2], … lui Cipri, acesta trebuind să le descifreze folosind convenția secretă stabilită la începutul prieteniei lor și să “acționeze”. Fiecare mesaj m[i] 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 m[i] și m[0] să conțină cel puțin un cuvânt identic având același număr de ordine în ambele mesaje. Din m[0] se păstrează toate cuvintele care se găsesc și în mesajul m[i] cu același număr de ordine ca în m[0].
Cuvintele păstrate trebuie ordonate în ordine descrescătoare lexicografică a puterii lor. Puterea cuvântului cu numărul de ordine j în m[0] este egală cu șirul ordonat descrescător al indicilor mesajelor în care apare cu același număr de ordine ca în m[0]. Astfel, un cuvânt care a apărut cu numărul de ordine 2 în mesajele m[0], m[6] și m[8] 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ța
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 m[0], m[1], m[2], …, 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 și 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 maximum
20de caractere, litere mici ale alfabetului englez. - Lungimea unui mesaj este de maximum
30002caractere. - Toate mesajele au acelaşi număr de cuvinte.
- Fișierul de intrare conține cel puțin unul și cel mult
128de 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.
Exemplul 1:
mesaje.in
inosos yy ataeclud ni a yy ataeclud ni yy inosos ni yy inosos bb ataeclud ni acni in e enib
mesaje.out
3 dulceata in sosoni
Explicație
Mesajele m[0] și m[4] nu conțin cuvinte identice cu același număr de ordine. Mesajele m[0] și m[3] 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}.
Exemplul 2:
mesaje.in
miras ep maeg
mesaje.out
3 sarim pe geam
Explicație
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.
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 mesaje:
#include <bits/stdc++.h>
using namespace std;
#define NMAX 129
#define MAXCUV 15001
#define LMAX 30010
char linie[LMAX], l0[LMAX];
char *m0[MAXCUV], *mi[MAXCUV];
int o[MAXCUV], oaux[MAXCUV];
unsigned long long vset2[MAXCUV][2];
int i, j, l, q, better, K, M, N;
void msort(int li, int ls)
{
int mid;
if (li < ls)
{
mid = (li + ls) >> 1;
msort(li, mid);
msort(mid + 1, ls);
i = li;
j = mid + 1;
l = li - 1;
while (i <= mid && j <= ls)
{
better = 0;
for (q = 0; q < 2; q++)
if (vset2[o[i]][q] > vset2[o[j]][q])
{
better = 1;
break;
}
else
if (vset2[o[i]][q] < vset2[o[j]][q])
{
better = - 1;
break;
}
l++;
if (better >= 0)
{
oaux[l] = o[i];
i++;
}
else
{
oaux[l] = o[j];
j++;
}
}
while (i <= mid)
{
l++;
oaux[l] = o[i];
i++;
}
while (j <= ls)
{
l++;
oaux[l] = o[j];
j++;
}
for (i = li; i <= ls; i++)
o[i] = oaux[i];
}
}
void solve(void)
{
int i, j, L, imax = 0;
freopen("mesaje.in", "r", stdin);
for (j = 0; j < MAXCUV; j++)
vset2[j][0] = vset2[j][1] = 0;
for (i = 0; 1; i++)
{
memset(&linie, 0, sizeof(linie));
fgets((char*)&linie, LMAX, stdin);
L = strlen(linie);
while (L > 0 && (linie[L] < 'a' || linie[L] > 'z'))
{
linie[L] = 0;
L--;
}
if (L == 0)
{
M = i;
break;
}
N = 1;
for (j = 1; j < L; j++)
if (linie[j] == ' ')
N++;
N = 1;
mi[0] = &linie[0];
for (j = 1; j < L; j++)
if (linie[j] == ' ')
{
linie[j] = 0;
mi[N] = &linie[j + 1];
N++;
}
if (i == 0)
{
memcpy(l0, linie, L + 1);
for (j = 0; j < N; j++)
m0[j] = l0 + (mi[j] - linie);
}
else
{
for (j = 0; j < N; j++)
{
if (!strcmp(mi[j], m0[j]))
{
imax = i;
if (i >= 64)
vset2[j][0] |= (1ULL << (i - 64));
else
vset2[j][1] |= (1ULL << i);
}
}
}
}
if (imax == 0)
{
K = N;
for (j = 0; j < N; j++)
o[j] = j;
}
else
{
K = 0;
for (j = 0; j < N; j++)
{
if ((imax >= 64 && (vset2[j][0] & (1ULL << (imax - 64)))) ||
(imax < 64 && (vset2[j][1] & (1ULL << (imax)))))
{
o[K] = j;
K++;
}
}
}
msort(0, K - 1);
}
void writeOutputData(void)
{
freopen("mesaje.out", "w", stdout);
printf("%d\n", K);
for (i = 0; i < K; i++)
{
if (i > 0)
printf(" ");
for (j = strlen(m0[o[i]]) - 1; j >= 0; j--)
printf("%c", m0[o[i]][j]);
}
printf("\n");
}
int main()
{
int tstart = clock();
solve();
writeOutputData();
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 #2382 mesaje
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2382 mesaje 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!