3904 - SeqCuts: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: == 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. == Date de intrare == Programul citește de la tastatură: Un șir de car...)
 
Fără descriere a modificării
 
(Nu s-a afișat o versiune intermediară efectuată de același utilizator)
Linia 1: Linia 1:
== Cerința ==
== 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 ==
== 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 ==
== 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 ==
== Restricții și precizări ==
*1 ⩽ '''text''' ⩽ 1000
*1 ≤ N ≤ 2.000.000
*1 ⩽ '''old_seq''' ⩽ 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 ==
== Exemplu 1 ==
;Intrare
;Intrare
SeqCuts este util<br>
10 3 2 <br>
util<br>
anaaremere
super


;Iesire
;Iesire
SeqCuts este super
aaae


Datele de intrare nu corespund restricțiilor impuse.
== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python" line>
<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__":
if __name__ == "__main__":
     main()
     main()


</syntaxhighlight>
</syntaxhighlight>

Versiunea curentă din 2 iunie 2024 22:10

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

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()
Adus de la „http://wiki.universitas.ro/index.php?title=3904_-_SeqCuts&oldid=9891”