3827 - C Bombs: Difference between revisions
Pagină nouă: ==Cerința== Le Quack vrea să bombardeze un oraș având N bombe numerotate de la 1...N. Dacă el detonează bombă cu valorea i atunci va putea să detoneze doar bombe încă nedetonate cu valori mai mici decât i. În cazul în care nu mai există astfel de bombe , poate detona orice bombă nedetonata. Le Quack va da numărul N și vrea să îi spuneți în câte moduri poate detona toate cele N bombe după regulă descrisă anterior. ==Date de intrare== Inputul conține... |
No edit summary |
||
| Line 29: | Line 29: | ||
În al doilea exemplu, configurațiile posibile sunt: [1 , 2 , 3] , [3 , 2 , 1] , [2 , 1 , 3] , [3 , 1 , 2] , [1 , 3 , 2]. Configurația [2 , 3 , 1] nu este bună, deoarece am luat bombă 3 înainte să termin toate bombele cu indici mai mici decât 2, ceea ce contrazice regula lui Le Quack. | În al doilea exemplu, configurațiile posibile sunt: [1 , 2 , 3] , [3 , 2 , 1] , [2 , 1 , 3] , [3 , 1 , 2] , [1 , 3 , 2]. Configurația [2 , 3 , 1] nu este bună, deoarece am luat bombă 3 înainte să termin toate bombele cu indici mai mici decât 2, ceea ce contrazice regula lui Le Quack. | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3"> | |||
MOD = 666013 | MOD = 666013 | ||
def numar_moduri_detonare(n): | def numar_moduri_detonare(n): | ||
DP = [0] * (n + 1) | |||
DP[0] = 1 | |||
for i in range(1, n + 1): | |||
for j in range(i): | |||
DP[i] = (DP[i] + DP[j]) % MOD | |||
return DP[n] | |||
if __name__ == "__main__": | |||
# Citim datele de intrare | |||
n = int(input()) | |||
# Calculăm rezultatul și afișăm rezultatul | |||
rezultat = numar_moduri_detonare(n) | |||
print(rezultat) | |||
</syntaxhighlight> | |||
Revision as of 17:42, 11 January 2024
Cerința
Le Quack vrea să bombardeze un oraș având N bombe numerotate de la 1...N. Dacă el detonează bombă cu valorea i atunci va putea să detoneze doar bombe încă nedetonate cu valori mai mici decât i. În cazul în care nu mai există astfel de bombe , poate detona orice bombă nedetonata. Le Quack va da numărul N și vrea să îi spuneți în câte moduri poate detona toate cele N bombe după regulă descrisă anterior.
Date de intrare
Inputul conține un număr natural n , reprezentând numărul de bombe pe care le are Le Quack.
Date de ieșire
Outputul conține răspunsul modulo 666013.
Restricții și precizări
N ≤ 2000. Pentru teste în valoare de 10p, N ≤ 9. Pentru restul testelor în valoare de 90p, N ≤ 2000. ==Exemplu==: bombs.in
2 bombs.out
2 bombs.in
3 bombs.out
5
Explicație
În primul exemplu, configurațiile posibile sunt: [1 , 2] și [2 , 1]. În al doilea exemplu, configurațiile posibile sunt: [1 , 2 , 3] , [3 , 2 , 1] , [2 , 1 , 3] , [3 , 1 , 2] , [1 , 3 , 2]. Configurația [2 , 3 , 1] nu este bună, deoarece am luat bombă 3 înainte să termin toate bombele cu indici mai mici decât 2, ceea ce contrazice regula lui Le Quack.
Rezolvare
<syntaxhighlight lang="python3"> MOD = 666013
def numar_moduri_detonare(n):
DP = [0] * (n + 1)
DP[0] = 1
for i in range(1, n + 1):
for j in range(i):
DP[i] = (DP[i] + DP[j]) % MOD
return DP[n]
if __name__ == "__main__":
# Citim datele de intrare n = int(input()) # Calculăm rezultatul și afișăm rezultatul rezultat = numar_moduri_detonare(n) print(rezultat)
</syntaxhighlight>