Olimpia D’Info a găsit o placă gravată ce conţine mai multe cuvinte scrise cu semne grafice necunoscute, fiecare cuvânt fiind format din exact 5 semne grafice. Studiind cu atenție cuvintele, a dedus că în scrierea acestora sunt utilizate 12 semne grafice distincte şi a asociat câte o literă mică din alfabetul englez fiecărui semn. După asociere, a stabilit pentru fiecare semn o complexitate, scriind literele în ordinea crescătoare a complexităților pe care le-a stabilit anterior. Olimpia consideră că această ”complexitate” este cel mai potrivit criteriu de ordonare lexicografică.
Cerinţe
Cunoscând ordinea semnelor și cuvintele de pe placă determinaţi:
Olimpia D’Info a găsit o placă gravată ce conţine mai multe cuvinte scrise cu semne grafice necunoscute, fiecare cuvânt fiind format din exact 5 semne grafice. Studiind cu atenție cuvintele, a dedus că în scrierea acestora sunt utilizate 12 semne grafice distincte şi a asociat câte o literă mică din alfabetul englez fiecărui semn. După asociere, a stabilit pentru fiecare semn o complexitate, scriind literele în ordinea crescătoare a complexităților pe care le-a stabilit anterior. Olimpia consideră că această ”complexitate” este cel mai potrivit criteriu de ordonare lexicografică.
Cerinţe
Cunoscând ordinea semnelor și cuvintele de pe placă determinaţi:
a) Numărul de cuvinte distincte existente pe placă.
b) Şirul de cuvinte ordonat lexicografic, conform criteriului formulat de Olimpia.
Date de intrare
Fișierul de intrare zimeria.in conține:
- pe prima linie un numărul natural
pdin{1,2}, reprezentând varianta cerinţei de rezolvare; - pe a doua linie un număr natural
nreprezentând numărul de cuvinte de pe placă; - pe a treia linie
12caractere, litere mici ale alfabetului englez, care reprezintă semnele codificate, în ordinea lexicografică a semnelor; - pe fiecare din următoarele
nlinii câte un cuvânt.
Date de ieșire
Dacă valoarea lui p este 1, atunci se va rezolva numai punctul a) din cerinţă. În acest caz, fişierul de ieşire zimeria.out va conţine pe prima linie numărul de cuvinte distincte de pe placă.
Dacă valoarea lui p este 2, atunci se va rezolva numai punctul b) din cerinţă. În acest caz, fişierul de ieşire zimeria.out va conţine n linii, pe fiecare linie câte un cuvânt în ordine lexicografică, conform complexităţii stabilite de către Olimpia.
Restricții și precizări
n < 400.000;- 30% din teste vor avea pe prima linie valoarea
1, iar restul de 70% din teste vor avea pe prima linie valoarea2.
Exemplul 1
zimeria.in
1 5 qwertyuiopas reeet wyuty reeet oiopp oiopp
zimeria.out
3
Explicație
Placa conţine 3 cuvinte distincte.
Exemplul 2
zimeria.in
2 5 qwertyuiopas reeet wyuty reeet oiopp oiopp
zimeria.out
wyuty reeet reeet oiopp oiopp
Explicație
Placa conţine 3 cuvinte distincte.
Ordonăm cuvintele și obținem wyuty, reeet, reeet, oiopp, oiopp.
#include <bits/stdc++.h>
using namespace std;
ifstream cin("zimeria.in");
ofstream cout("zimeria.out");
int f[13][13][13][13][13];
char s[13];
int poz(char ch)
{
int i = 0;
while(s[i]!='\0')
{
if(s[i]==ch)
return i;
i++;
}
}
int main()
{
int tr , q;
cin >> tr >> q;
cin >> s;
char a , b , c , d , e;
while(cin >> a)
{
cin >> b >> c >> d >> e;
f[poz(a)][poz(b)][poz(c)][poz(d)][poz(e)]++;
}
if(tr == 1)
{
int cnt = 0;
for(int i = 0 ; i <= 11 ; ++i)
for(int j = 0 ; j <= 11 ; ++j)
for(int k = 0 ; k <= 11 ; ++k)
for(int t = 0 ; t <= 11 ; ++t)
for(int w = 0 ; w <= 11 ; ++w)
if(f[i][j][k][t][w])
cnt++;
cout << cnt;
return 0;
}
for(int i = 0 ; i <= 11 ; ++i)
for(int j = 0 ; j <= 11 ; ++j)
for(int k = 0 ; k <= 11 ; ++k)
for(int t = 0 ; t <= 11 ; ++t)
for(int w = 0 ; w <= 11 ; ++w)
if(f[i][j][k][t][w])
for(int g = 0 ; g < f[i][j][k][t][w] ; ++g)
cout << s[i] << s[j] << s[k] << s[t] << s[w] << '\n';
return 0;
}
