3904 - SeqCuts

Cerința

Se dă un șir de N caractere, format din litere mici ale alfabetului englez, din care trebuie eliminate K secvențe disjuncte de lungime L. Care este cel mai mic şir din punct de vedere lexicografic ce se poate obține după eliminarea celor K secvențe.

Date de intrare

Prima linie conține numărul de caractere N al şirului, numărul K al secvențelor care trebuie eliminate şi numărul L al lungimii unei secvențe ce trebuie eliminate. Cea de-a doua linie conţine N litere mici ale alfabetului englez, neseparate prin spaţii.

Date de ieșire

Programul va afișa pe ecran cel mai mic şir din punct de vedere lexicografic ce se poate obține după eliminările făcute.

Restricții și precizări

• 1 ≤ N ≤ 2.000.000
• 0 ≤ K * L < N
• șirul de caractere este format din litere mici ale alfabetului englez

Exemplu 1

Intrare

10 3 2
anaaremere

Iesire

aaae

Rezolvare

<syntaxhighlight lang="python" line> def main():

   # Citirea datelor de intrare
   N, K, L = map(int, input().strip().split())
   sir = input().strip()

   # Verificăm restricțiile
   assert 1 <= N <= 2000000, "N trebuie sa fie intre 1 si 2.000.000"
   assert 0 <= K * L < N, "0 <= K * L < N trebuie să fie adevărat"
   assert all('a' <= c <= 'z' for c in sir), "Șirul trebuie să conțină doar litere mici ale alfabetului englez"

   # Calculăm lungimea finală a șirului după eliminarea K secvențe de lungime L
   lungime_finala = N - K * L
   stiva = []
   eliminari = 0

   for i, caracter in enumerate(sir):
       while stiva and eliminari < K * L and stiva[-1] > caracter and len(stiva) + len(sir) - i - 1 >= lungime_finala:
           stiva.pop()
           eliminari += 1
       if len(stiva) < lungime_finala:
           stiva.append(caracter)
       else:
           eliminari += 1

   print("".join(stiva))

if __name__ == "__main__":

   main()

</syntaxhighlight>