3222 - treasure

Enunt

Andrei este un aventurier care a plecat în căutarea unei comori pline cu bănuți de aur. Când a ajuns la ultimul indiciu, cel care ii va spune în ce loc se află comoara, a văzut ca pe indiciu sunt scrise doua numere naturale N și K, iar pe a doua linie un sir de N caractere, litere mici ale alfabetului englez. Andrei trebuie să ia șirul curent și să elimine prima secvență de K litere identice care apar pe poziții consecutive. El va relua acest procedeu până când nu va mai exista nicio secvență de K litere identice consecutive. Andrei vă roagă să-l ajutați să rezolve cât mai repede această problemă pentru a putea ajunge primul la comoară.

Cerința

Fiind date N și K, numere naturale și un șir de N litere mici ale alfabetului englez, trebuie să eliminați mereu prima secvență de K caractere identice aflate pe poziții consecutive până nu va mai exista nicio astfel de secvență.

Date de intrare

Se vor citi de la tastatura pe prima linie două numere naturale N și K, iar pe a doua linie un sir de N litere mici ale alfabetului englez.

Date de ieșire

Se va afișa pe ecran un sir care reprezintă șirul final pe care îl obținem după ce am efectuat toate eliminările posibile. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 2 ≤ K ≤ N ≤ 200.000
• Toate caracterele șirului inițial sunt litere mici ale alfabetului englez
• Se garantează că la final șirul nu va fi vid!

Exemplul 1:

Intrare

5 2
abbac

Ieșire

c

Explicație

Șirul inițial : abbac

Șirul după prima eliminare: aac

Șirul după a doua eliminare: c

Exemplul 2:

Intrare

1 1
1

Ieșire

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def check_restrictions(n, k, s):

   if not (2 <= k <= n <= 200000):
       return False
   s_str = .join(s)
   if not s_str.islower():
       return False
   if not s:
       return False
   return True

def main():

   n, k = map(int, input().split())
   s = list(input())
   if not check_restrictions(n, k, s):
       print("Datele nu corespund restrictiilor impuse")
       return
   ok = 0
   while ok == 0:
       ctm = 1
       ok = 1
       elem = 0
       rez = [0] * (n + 1)
       for x in range(n):
           elem += 1
           rez[elem] = s[x]
           if x < n - 1 and s[x] == s[x + 1]:
               ctm += 1
           else:
               if ctm >= k:
                   elem -= k
                   ok = 0
               ctm = 1
       if ctm >= k:
           elem -= k
       s = ['\0'] * n
       for x in range(1, elem + 1):
           s[x - 1] = rez[x]
       n = elem
   for x in range(1, elem + 1):
       print(rez[x], end="")
   print()

if __name__ == "__main__":

   main()

</syntaxhighlight>