criptografie

Time limit: 0.2s Memory limit: 20MB Input: criptografie.in Output: criptografie.out

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ță

Cunoscând textul lui Zedd, să se determine:

  1. Numărul de secvențe distincte în care fiecare literă poate să apară de maximum kk ori. Două secvențe sunt considerate distincte dacă diferă fie prin poziția de început, fie prin cea de final.
  2. 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 CC (care poate fi 11 sau 22), pe linia a doua numărul natural kk, cu semnificația de mai sus, precum și un număr natural nn, separate printr-un spațiu. Pe a treia linie se află un text format din nn 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=1C=1, un număr natural ce reprezintă răspunsul la cerința 1.
  • Dacă C=2C=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<n1050 \lt n \leq 10^5;
  • 0<kn0 \lt k \leq n;
  • Pentru teste în valoare de 67 de puncte C=1C = 1, iar pentru 33 de puncte C=2C = 2;
  • Pentru teste în valoare de 17 puncte se garantează C=1C = 1, k=1k = 1 și n100n \leq 100;
  • Pentru teste în valoare de alte 17 puncte se garantează C=1C = 1 și n1 000n \leq 1 \ 000;
  • Pentru cerința 2 se garantează că valoarea lui kk este 11.

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=1k = 1) ce pot fi formate este 88.

Exemplul 2

criptografie.in

2
1 6
abacba

criptografie.out

acb

Explicație

Lungimea maximă a unei secvențe de elemente distincte este 33. Sunt trei astfel de secvențe. Prima din punct de vedere alfabetic este acb.

Log in or sign up to be able to send submissions!