3904 - SeqCuts: Difference between revisions

Latest revision as of 22:10, 2 June 2024

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>

@@ Line 1: / Line 1: @@
 == Cerința ==
-Într-un tărâm digital, există o aplicație numită SeqCuts, care ajută programatorii să manipuleze și să analizeze siruri de caractere. Programatorii pot folosi SeqCuts pentru a găsi și a înlocui secvențe de caractere în cadrul unui text. Sarcina este de a implementa această funcționalitate pentru a ajuta utilizatorii să manipuleze siruri de caractere conform cerințelor.
+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 ==
-Programul citește de la tastatură:
+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.
-Un șir de caractere text reprezentând textul original.
-Un șir de caractere old_seq reprezentând secvența de înlocuit.
-Un șir de caractere new_seq reprezentând secvența cu care se înlocuiește.
 == Date de ieșire ==
-Pe ecran se va afișa textul modificat în care toate aparițiile secvenței old_seq au fost înlocuite cu new_seq.
+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 &les; '''text''' &les; 1000
+*1 ≤ N ≤ 2.000.000
-*1 &les; '''old_seq''' &les; 100
+*0 ≤ K * L < N
-*1 &les; '''new_seq''' &les; 100
+*șirul de caractere este format din litere mici ale alfabetului englez
-old_seq si new_seq pot contine orice caractere.
 == Exemplu 1 ==
 ;Intrare
-SeqCuts este util<br>
+3 2 <br>
-util<br>
+anaaremere
-super
 ;Iesire
-SeqCuts este super
+aaae
-Datele de intrare nu corespund restricțiilor impuse.
 == Rezolvare ==
 <syntaxhighlight lang="python" line>
-def citeste_date():
+def main():
-     text = input("Introduceți textul original: ")
+     # Citirea datelor de intrare
-     old_seq = input("Introduceți secvența de înlocuit: ")
+    N, K, L = map(int, input().strip().split())
-    new_seq = input("Introduceți secvența nouă: ")
+     sir = input().strip()
-    return text, old_seq, new_seq
-def valideaza_date(text, old_seq, new_seq):
+    # Verificăm restricțiile
-     if 1 <= len(text) <= 1000 and 1 <= len(old_seq) <= 100 and 1 <= len(new_seq) <= 100:
+     assert 1 <= N <= 2000000, "N trebuie sa fie intre 1 si 2.000.000"
-        return True
+    assert 0 <= K * L < N, "0 <= K * L < N trebuie să fie adevărat"
-    return False
+    assert all('a' <= c <= 'z' for c in sir), "Șirul trebuie să conțină doar litere mici ale alfabetului englez"
-def inlocuieste_secventa(text, old_seq, new_seq):
+    # Calculăm lungimea finală a șirului după eliminarea K secvențe de lungime L
-     text_modificat = text.replace(old_seq, new_seq)
+     lungime_finala = N - K * L
-     return text_modificat
+     stiva = []
+    eliminari = 0
-def main():
+    for i, caracter in enumerate(sir):
-    text, old_seq, new_seq = citeste_date()
+        while stiva and eliminari < K * L and stiva[-1] > caracter and len(stiva) + len(sir) - i - 1 >= lungime_finala:
+            stiva.pop()
-    if not valideaza_date(text, old_seq, new_seq):
+            eliminari += 1
-        print("Datele de intrare nu corespund restricțiilor impuse.")
+        if len(stiva) < lungime_finala:
-         return
+            stiva.append(caracter)
+         else:
-     print("Datele de intrare corespund restricțiilor impuse.")
+            eliminari += 1
-    text_modificat = inlocuieste_secventa(text, old_seq, new_seq)
-    print(text_modificat)
+     print("".join(stiva))
 if __name__ == "__main__":
      main()
 </syntaxhighlight>