View source for 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| =

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

= 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

'''''<u>Rezolvare</u>'''''<syntaxhighlight lang="python">
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()
</syntaxhighlight>