Editing 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">
#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>