2882 - No Pals: Difference between revisions
Pagină nouă: ==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==... |
No edit summary |
||
| Line 22: | Line 22: | ||
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. | 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== | ==Rezolvare== | ||
<syntaxhighlight lang="python3"> | |||
MOD = 666013 | MOD = 666013 | ||
def numere_nepalindromice(n): | 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__": | 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") | |||
</syntaxhighlight> | |||
Revision as of 17:30, 11 January 2024
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
<syntaxhighlight lang="python3"> 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")
</syntaxhighlight>