Editing 2036 - Numele animalutului lui Arpsod

De ziua lui, vrăjitorul Arpsod a primit în dar un animăluț mic și pufos. Evident, acesta dorește să îi dea un nume. Pentru a fi protejat de răul și blaturile existente în Univers, Arpsod a decis să îi dea un nume strict legat de numărul său protector. Cunoscând numărul protector, numele animăluțului se va determina astfel: Va fi un șir de litere MARI ale alfabetului latin, de lungime minimă cu proprietatea că suma diferențelor în modul a literelor vecine este egală cu numărul lui Arpsod.

Concret: dacă avem numele FLAFFY, obținem:

|F – L| + |L – A| + |A – F| + |F – F| + |F – Y| =

<nowiki>= |6 – 12| + |12 – 1| + |1 – 6| + |6 – 6| + |6 – 25|=</nowiki>

= 6 + 11 + 5 + 0 + 19 = 41

Deci codul numelui FLAFFY este 41

'''''<u>Cerința</u>'''''

Arpsod vă oferă onoarea de a afla numele micuțului său animăluț.

'''''<u>Date de intrare</u>'''''

În fișierul nume1.in, pe prima și singura linie, se va afla P, numărul protector dat de Arpsod.

'''''<u>Date de ieșire</u>'''''

În fișierul nume1.out, pe prima și singura linie se va afișa un șir de litere MARI ale alfabetului latin, cu proprietățile cerute în enunț.

'''''<u>Restricții și precizări</u>'''''

1 ≤ P ≤ 4.000.000

A = 1, B = 2, C = 3… Z = 26

În cazul în care șirul afișat are suma corectă și număr minim de caractere, primiți 20% din punctajul pe acel test.

Dacă șirul afișat are proprietățile de mai sus și este și minim lexicografic, primiți punctajul integral pe acel test.

Un șir A este mai mic lexicografic decât un șir B dacă pe prima poziție unde A[i] ≠ B[i], A[i] < B[i].

'''''<u>Exemplu:</u>'''''

nume1.in

19

808

nume1.out

AT

ARAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAY

'''''<u>Explicație</u>'''''

În primul exemplu: A = 1, T = 20, |A – T| = |1 – 20| = 19

'''''<u>Rezolvare</u>'''''<syntaxhighlight lang="python">
def pot_pune(trebuie, c, last, lungime_optima, lungime_curenta):
    # Calculează suma necesară pentru a adăuga caracterul 'c'
    sum = abs(ord(last) - ord(c))
    ramase = lungime_optima - lungime_curenta - 1

    # Dacă mai sunt caractere de adăugat, calculează suma adăugând 'A' sau 'Z' în funcție de care este mai departe de 'c'
    if ramase > 0:
        sum += max(abs(ord(c) - ord('A')), abs(ord(c) - ord('Z')))
        ramase -= 1

    # Adaugă suma pentru restul caracterelor care vor fi 'A' și 'Z' alternativ
    sum += ramase * 25

    # Verifică dacă suma obținută este suficientă
    return sum >= trebuie


def main():
    # Deschide fișierul de intrare  și fișierul de ieșire 
    with open("nume1in.txt", "r") as fin, open("nume1out.txt", "w") as fout:
        # Citește suma cerută pentru șir
        N = int(fin.readline().strip())

        # Calculează lungimea optimă a șirului
        lungimea_optima = (N // 25) + 1 + (N % 25 != 0)

        # Inițializează ultimul caracter adăugat cu 'A'
        last = 'A'

        # Inițializează lungimea curentă a șirului cu 1
        lungime_curenta = 1

        # Adaugă primul caracter în fișierul de ieșire
        fout.write('A')

        suma = 0

        # Cat timp nu am atins lungimea optimă a șirului
        while lungime_curenta < lungimea_optima:
            # Încercă să adaugi fiecare caracter
            for i in range(ord('A'), ord('Z') + 1):
                i = chr(i)

                # Verifică dacă caracterul poate fi adăugat
                if pot_pune(N - suma, i, last, lungimea_optima, lungime_curenta):
                    # Dacă este ultimul caracter și adăugarea lui nu atinge exact suma cerută, treci la următorul caracter
                    if lungime_curenta == lungimea_optima - 1 and suma + abs(ord(last) - ord(i)) != N:
                        continue

                    # Adaugă la suma diferența dintre ultimul caracter și caracterul curent
                    suma += abs(ord(last) - ord(i))

                    # Adaugă caracterul în fișierul de ieșire
                    fout.write(i)

                    # Incrementez lungimea curentă a șirului
                    lungime_curenta += 1

                    # Caracterul adăugat devine ultimul caracter
                    last = i
                    break

if __name__ == "__main__":
    main()
</syntaxhighlight>