Zedd a descoperit frumusețea aplicațiilor din domeniul criptografiei. Astfel, el și-a activat abilitățile de hacker și s-a lovit de următoarea problemă: fiind dat un șir format doar din litere mici ale alfabetului englez, Zedd trebuie să găsească secvențe pe care le poate forma fără ca vreo literă să apară de prea multe ori.
Cerința
Cunoscând textul lui Zedd, să se determine:
- Numărul de secvențe distincte în care fiecare literă poate să apară de maximum
k
ori. Două secvențe sunt considerate distincte dacă diferă fie prin poziția de început, fie prin cea de final. - Cea mai lungă secvență care conține doar litere distincte. Dacă sunt mai multe secvențe de lungime maximă formate din litere distincte se alege prima din punct de vedere lexicografic (alfabetic).
Date de intrare
Fișierul de intrare criptografie.in
conține pe prima linie cerința C
(care poate fi 1
sau 2
), pe linia a doua numărul natural k
, cu semnificația de mai sus, precum și un număr natural n
, separate printr-un spațiu. Pe a treia linie se află un text format din n
litere mici ale alfabetului englez (neseparate prin spații).
Date de ieșire
Fișierul de ieșire criptografie.out
va conține pe prima linie:
Dacă C = 1
un număr natural ce reprezintă răspunsul la cerința 1
.
Dacă C = 2
șirul ce reprezintă răspunsul la cerința 2
.
Restricții și precizări
- o secvență este formată dintr-o succesiune de litere aflate pe poziții consecutive într-un șir.
0 < n ≤ 100.000
0 < k ≤ n
- Pentru teste în valoare de
67
de puncteC = 1
, iar pentru33
de puncteC = 2
- Pentru teste în valoare de
17
puncte se garanteazăC = 1
,k = 1
șin ≤ 100
- Pentru teste în valoare de alte
17
puncte se garanteazăC = 1
șin ≤ 1000
- Pentru cerința
2
se garantează că valoarea luik
este1
.
Exemplul 1:
criptografie.in
1 1 4 abac
criptografie.out
8
Explicație
Pentru textul dat, variantele care ar putea fi obținute conform cerinței sunt: a
, ab
, b
, ba
, bac
, a
, ac
, c
. În total numărul de secvențe cu caractere distincte (k = 1
) ce pot fi formate este 8
.
Exemplul 2:
criptografie.in
2 1 6 abacba
criptografie.out
acb
Explicație
Lungimea maximă a unei secvențe de elemente distincte este 3
. Sunt trei astfel de secvențe. Prima din punct de vedere alfabetic este acb
.
#include <fstream> #include <cstring> using namespace std; long long sol; char s[100010]; int c, k, n, i, p, maxim; char ch; char smaxim[27]; int f[26]; int main () { ifstream fin ("criptografie.in"); ofstream fout("criptografie.out"); fin>>c; fin>>k>>n; for (i=1;i<=n;i++) fin>>s[i]; p = 1; strcpy(smaxim, "zz"); for (i=1;i<=n;i++) { ch = s[i]-'a'; f[ ch ] ++; while ( f[ch] > k ) { f[ s[p]-'a' ]--; p++; } if (c == 1) sol += i-p+1; else { if (i-p+1 > maxim) { maxim = i-p+1; strncpy(smaxim, s+p, maxim); } else if (i-p+1 == maxim) if (strncmp(smaxim, s+p, maxim) > 0) strncpy(smaxim, s+p, maxim); } } if (c == 1) fout<<sol; else { smaxim[maxim] = 0; fout<<smaxim; } return 0; }