3033 - criptografie

Enunț

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 criptografiein.txt 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 criptografieout.txt 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 puncte C = 1, iar pentru 33 de puncte C = 2
• Pentru teste în valoare de 17 puncte se garantează C = 1, k = 1 și n ≤ 100
• Pentru teste în valoare de alte 17 puncte se garantează C = 1 și n ≤ 1000
• Pentru cerința 2 se garantează că valoarea lui k este 1.

Exemplul 1

criptografiein.txt

1

1 4

abac

criptografieout.txt

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

criptografiein.txt

2

1 6

abacba

criptografieout.txt

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.

Rezolvare

<syntaxhighlight lang="python"> def validate_input(c, k, n):

   if not (0 < n <= 100000):
       raise ValueError("Valoare invalidă pentru n. Se cere 0 < n <= 100000.")
   if not (0 < k <= n):
       raise ValueError("Valoare invalidă pentru k. Se cere 0 < k <= n.")

def main():

   with open("criptografiein.txt", "r") as fin, open("criptografieout.txt", "w") as fout:
       c = int(fin.readline().strip())
       k, n = map(int, fin.readline().split())
       s = fin.readline().strip()

       sol = 0
       p = 0
       maxim = 0
       smaxim = 'z' * 27
       f = [0] * 26

       for i in range(n):
           ch = ord(s[i]) - ord('a')
           f[ch] += 1

           while f[ch] > k:
               f[ord(s[p]) - ord('a')] -= 1
               p += 1

           if c == 1:
               sol += i - p + 1
           else:
               if i - p + 1 > maxim:
                   maxim = i - p + 1
                   smaxim = s[p:p + maxim]
               elif i - p + 1 == maxim and smaxim > s[p:p + maxim]:
                   smaxim = s[p:p + maxim]

       if c == 1:
           fout.write(str(sol))
       else:
           fout.write(smaxim)

if __name__ == "__main__":

   main()

</syntaxhighlight>