2036 - Numele animalutului lui Arpsod

Enunț

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| =

= |6 – 12| + |12 – 1| + |1 – 6| + |6 – 6| + |6 – 25|=

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

Deci codul numelui FLAFFY este 41

Cerința

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

Date de intrare

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

Date de ieșire

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

Restricții și precizări

• 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].

Exemplu:

nume1in.txt

19

808

nume1out.txt

AT

ARAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAY

Explicație

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

Rezolvare

def pot_pune(trebuie, c, last, lungime_optima, lungime_curenta):
    suma = abs(ord(last) - ord(c))
    ramase = lungime_optima - lungime_curenta - 1

    if ramase > 0:
        suma += max(abs(ord(c) - ord('A')), abs(ord(c) - ord('Z')))
        ramase -= 1

    suma += ramase * 25

    return suma >= trebuie


def validare_date(P):
    if 1 <= P <= 4000000:
        return True
    else:
        print("Eroare: P trebuie să fie în intervalul [1, 4.000.000]")
        return False


def main():
    with open("nume1in.txt", "r") as fin, open("nume1out.txt", "w") as fout:
        P = int(fin.readline().strip())
        if not validare_date(P):
            return

        N = int(fin.readline().strip())
        lungimea_optima = (N // 25) + 1 + (N % 25 != 0)
        last = 'A'
        lungime_curenta = 1
        fout.write('A')

        suma = 0

        while lungime_curenta < lungimea_optima:
            for i in range(ord('A'), ord('Z') + 1):
                i = chr(i)

                if pot_pune(N - suma, i, last, lungimea_optima, lungime_curenta):
                    if lungime_curenta == lungimea_optima - 1 and suma + abs(ord(last) - ord(i)) != N:
                        continue

                    suma += abs(ord(last) - ord(i))
                    fout.write(i)
                    lungime_curenta += 1
                    last = i
                    break

if __name__ == "__main__":
    main()