Editing 1133 - Charlie

== Enunt ==

Charlie a decis să se joace cu literele dintr-un șir de caractere, șir ce conține doar literele mici ale alfabetului englez <code>'a'...'z'</code>. Jocul constă în a elimina litere din șir după următoarea regulă: fie <code>L1</code>, <code>L2</code>, <code>L3</code> trei litere aflate pe poziții consecutive în șir, atunci litera <code>L2</code> poate fi eliminată dacă și numai dacă este strict mai mică lexicografic decât literele <code>L1</code> și <code>L3</code>.

Pentru a face jocul mai interesant, Charlie atașează eliminării literei <code>L2</code> un cost egal cu valoarea maximă dintre <code>ō(L1)</code> și <code>ō(L3)</code>, unde prin <code>ō(litera)</code> înțelegem numărul de ordine al literei respective în alfabet (<code>ō('a') = 1</code>, <code>ō('b') = 2</code>, …, <code>ō('z') = 26</code>). Charlie aplică în mod repetat procedeul de eliminare și calculează suma costurilor eliminărilor efectuate.

= Cerinţe =
Fiind dat un șir de caractere să se determine:

a) Lungimea maximă a unei secvențe de litere alternante, adică o secvență pentru care literele aflate pe poziții consecutive sunt de forma: <code>Li</code> <code>> Li+1</code> <code>< Li+2</code> <code>> Li+3</code> <code>< Li+4</code> <code>> … < Lj</code>.

b) Suma maximă pe care o poate obține Charlie aplicând în mod repetat procedeul de eliminare a literelor, precum și șirul obținut în final.

= Date de intrare =
Fișierul de intrare <code>charlie.in</code> conține pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale separate prin spații.

= Date de ieșire =
Dacă valoarea lui <code>p</code> este <code>1</code>, se va rezolva numai punctul a) din cerință.

În acest caz, în fişierul de ieşire <code>charlieIN.txt</code> se va scrie un singur număr natural <code>L</code> ce reprezintă lungimea maximă a unei secvențe de litere alternante.

Dacă valoarea lui <code>p</code> este <code>2</code>, se va rezolva numai punctul b) din cerință.

În acest caz, fişierul de ieşire <code>charlieOUT.txt</code> va conține două linii. Pe prima linie se va afla șirul rezultat în urma eliminărilor repetate de litere respectând regula enunțată, iar pe cea de-a doua linie suma maximă obținută. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>3 ≤</code> numărul de litere ale șirului inițial <code>≤ 100000</code>
* Pentru rezolvarea corectă a primei cerinţe se acordă 25 de puncte, iar pentru cerința a doua se acordă 75 de puncte. Pentru 30% dintre teste numărul de litere ale șirului <code>≤ 1000</code>

= Exemplul 1: =
<code>charlieIN.txt</code>
 1
 cadgfacbda
<code>charlieOUT.txt</code>
 5

= Explicație =
<code>p = 1</code>

Secvențele alternante corect formate sunt: <code>cad</code>, <code>facbd</code>. Lungimea maximă este <code>5</code>.

== Exemplul 1: ==
<code>charlieIN.txt</code>
 1
 ca
<code>charlieOUT.txt</code>
 Datele nu corespund restrictiilor impuse
:

== Rezolvare == 
<syntaxhighlight lang="python3" line="1">
ordine = 96

def verify_restrictions(length):
    if length < 3 or length > 100000:
        return "Datele nu corespund restrictiilor impuse"
    return None

def read():
    with open("charlieIN.txt", "r") as cin:
        lines = cin.readlines()
        task = int(lines[0])
        v = [ord(c) for c in lines[1].strip()]  # Convert characters to their ASCII values
        n = len(v)

        # Verificare restricții
        restriction_error = verify_restrictions(n)
        if restriction_error:
            with open("charlieOUT.txt", "w") as cout:
                cout.write(restriction_error)
            return None, None, None

        return task, v, n

def solve1(v, n):
    lmax = l = t = 0
    start = False
    i = 0
    t = 1

    while i < n - 1:
        if not start:
            if v[i] * t > v[i + 1] * t:
                start = True
                l = 2
                t *= -1
            i += 1
        else:
            if v[i] * t > v[i + 1] * t:
                l += 1
                t *= -1
                i += 1
            else:
                if t == -1:
                    l -= 1
                lmax = max(lmax, l)
                l = 0
                start = False
                t = 1

    if l and t == -1:
        l -= 1

    lmax = max(lmax, l)

    return lmax

def parcurgere(v, n):
    i = k = r = 0
    modificari = False
    new_v = [v[0]]
    cost = 0

    i = 1
    while i < n - 1:
        while i < n - 1 and v[i] < min(new_v[k], v[i + 1]):
            cost += max(new_v[k], v[i + 1]) - ordine
            modificari = True
            i += 1
            r += 1
        new_v.append(v[i])
        k += 1
        i += 1

    new_v.append(v[n - 1])
    n = len(new_v)

    return modificari, new_v, n, cost

def solve2(v, n):
    ok = True
    total_cost = 0

    while ok:
        ok, v, n, cost = parcurgere(v, n)
        total_cost += cost

    return ''.join([chr(c) for c in v]), total_cost

def main():
    task, v, n = read()
    if task is not None:
        if task % 2:
            result = solve1(v, n)
        else:
            result, cost = solve2(v, n)
            result = f"{result}\n{cost}"
        
        with open("charlieOUT.txt", "w") as cout:
            cout.write(str(result))

if __name__ == "__main__":
    main()

</syntaxhighlight>