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

Cerinta

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 iesire

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.

Restrictii si precizari

• 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

iesire

Datele introduse corespund restrictiilor impuse.

c

Exemplul 2

intrare

3 6

bbaaabbaabbc

iesire

baabbc

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1">

1. 3222 - treasure

def eliminate_sequences(n, k, sequence):

   modified = True

   while modified:
       modified = False
       i = 0

       while i < len(sequence):
           count = 1
           j = i + 1

           while j < len(sequence) and sequence[j] == sequence[i]:
               count += 1
               j += 1

           if count >= k:
               sequence = sequence[:i] + sequence[i + k:]
               modified = True
           else:
               i = j

   return sequence

result = eliminate_sequences(N, K, sequence) print("Șirul rezultat după eliminarea secvențelor de lungime", K, "este:", result)

</syntaxhighlight>