2882 - No Pals

Cerința

Gioni este un elev foarte pasionat de informatică și îndrăgește în special problemele care se rezolvă cu tehnica programării dinamice. El are un număr natural n și vrea să știe pentru fiecare numar i de la 1 la n câte numere cu i cifre nu sunt palindromuri. Fiindcă acest număr poate să fie foarte mare, se cere afișarea lui modulo 666013.

Date de intrare

Fișierul de intrare no_pals.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire no_pals.out va conține pe fiecare linie i, de la 1 la n, numărul de numere de i cifre care nu sunt palindromuri.

Restricții și precizări

1 ≤ n ≤ 100000 Exemplu: no_pals.in

3 no_pals.out

0 81 810

Explicație

Toate numerele de o cifra sunt palindromuri. Sunt 90 de numere de 2 cifre, dintre care 9 sunt palindromuri. Sunt 900 de numere de 3 cifre, dintre care 90 sunt palindromuri.

Rezolvare

MOD = 666013

def numere_nepalindromice(n):

   dp = [0] * (n + 1)
   dp[1] = 9  # Un singur caracter, 9 opțiuni ne-palindromice (de la 1 la 9)
   for i in range(2, n + 1):
       dp[i] = (dp[i - 1] * 9) % MOD  # Numărul de opțiuni pentru i cifre
   return dp

if __name__ == "__main__":

   with open("no_pals.in", "r") as f:
       n = int(f.readline().strip())
   rezultate = numere_nepalindromice(n)
   with open("no_pals.out", "w") as g:
       for rezultat in rezultate[1:]:
           g.write(str(rezultat) + "\n")