3827 - C Bombs - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:34:36Z

Rezolvare

← Older revision		Revision as of 18:34, 11 January 2024
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">		<syntaxhighlight lang="python3" line="1">
	MOD = 666013		MOD = 666013

Mraa at 17:42, 11 January 2024

2024-01-11T17:42:19Z

← Older revision		Revision as of 17:42, 11 January 2024
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):		DP = [0] * (n + 1)
	for j in range(i):		DP[0] = 1
	DP[i] = (DP[i] + DP[j]) % MOD		for i in range(1, n + 1):
			for j in range(i):
			DP[i] = (DP[i] + DP[j]) % MOD
			return DP[n]

	~~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)

	~~if __name__ == "__main__":~~
	~~# Citim datele de intrare~~
	~~n = int(input())~~

	~~# Calculăm rezultatul și afișăm rezultatul~~		</syntaxhighlight>
	~~rezultat = numar_moduri_detonare(n)~~
	~~print(rezultat)~~
	~~python bombs.py~~

Mraa: 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...

2023-12-21T21:29:31Z

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

New page

==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==
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)
python bombs.py