3639 - Subset Fight - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:34:02Z

Rezolvare

← Older revision		Revision as of 18:34, 11 January 2024
Line 37:		Line 37:
	985611225		985611225
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	MOD = 10**9 + 7		MOD = 10**9 + 7

Mraa at 17:41, 11 January 2024

2024-01-11T17:41:37Z

← Older revision		Revision as of 17:41, 11 January 2024
Line 37:		Line 37:
	985611225		985611225
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	MOD = 10**9 + 7		MOD = 10**9 + 7

	def numar_submultimi(n, v):		def numar_submultimi(n, v):
	~~# Inițializăm tabelul DP cu 0~~
	~~DP = [[0] * n for _ in range(2)]~~

	# Setăm valoarea inițială pentru submulțimile vide		# Inițializăm tabelul DP cu 0
	DP[0][0] = 1		DP = [[0] * n for _ in range(2)]
			# Setăm valoarea inițială pentru submulțimile vide
	for i in range(1, n + 1):		DP[0][0] = 1
	# Trecem la o nouă matrice DP (pară/impară)		for i in range(1, n + 1):
	current = i % 2		# Trecem la o nouă matrice DP (pară/impară)
	previous = 1 - current		current = i % 2
			previous = 1 - current
	for j in range(n):		for j in range(n):
	# Copiem valorile din matricea anterioară		# Copiem valorile din matricea anterioară
	DP[current][j] = DP[previous][j]		DP[current][j] = DP[previous][j]
			# Actualizăm matricea curentă adăugând valorile corespunzătoare din vector
	# Actualizăm matricea curentă adăugând valorile corespunzătoare din vector		DP[current][(j + i) % n] = (DP[current][(j + i) % n] + DP[previous][j]) % MOD
	DP[current][(j + i) % n] = (DP[current][(j + i) % n] + DP[previous][j]) % MOD		return DP[n % 2][0] - 1

	return DP[n % 2][0] - 1

	if __name__ == "__main__":		if __name__ == "__main__":
	~~# Citim datele de intrare~~
	~~n = int(input())~~
	~~v = list(map(int, input().split()))~~

	# Calculăm rezultatul și afișăm rezultatul		# Citim datele de intrare
	rezultat = numar_submultimi(n, v)		n = int(input())
	print(rezultat)		v = list(map(int, input().split()))
	~~python combatanti.py~~		# Calculăm rezultatul și afișăm rezultatul
			rezultat = numar_submultimi(n, v)
			print(rezultat)
			</syntaxhighlight>

Mraa: Pagină nouă: ==Cerința== Un război se apropie, va trebui să ajuți combatanții să afle șansele lor de victorie. Se dă un vector cu n numere naturale, unde v[i] reprezintă numărul de valori egale cu i. Un scenariu în care omenirea câștigă e un scenariu în care suma numerelor dintr-o submulțime este multiplu de n. De exemplu, dacă vectorul din enunț este 1 2 3, valorile pe care le avem de fapt sunt 1 2 2 3 3 3, valori pe care le putem nota ca facând parte dintr-un nou ve...

2023-12-21T21:27:35Z

Pagină nouă: ==Cerința== Un război se apropie, va trebui să ajuți combatanții să afle șansele lor de victorie. Se dă un vector cu n numere naturale, unde v[i] reprezintă numărul de valori egale cu i. Un scenariu în care omenirea câștigă e un scenariu în care suma numerelor dintr-o submulțime este multiplu de n. De exemplu, dacă vectorul din enunț este 1 2 3, valorile pe care le avem de fapt sunt 1 2 2 3 3 3, valori pe care le putem nota ca facând parte dintr-un nou ve...

New page

==Cerința==
Un război se apropie, va trebui să ajuți combatanții să afle șansele lor de victorie.

Se dă un vector cu n numere naturale, unde v[i] reprezintă numărul de valori egale cu i. Un scenariu în care omenirea câștigă e un scenariu în care suma numerelor dintr-o submulțime este multiplu de n.

De exemplu, dacă vectorul din enunț este 1 2 3, valorile pe care le avem de fapt sunt 1 2 2 3 3 3, valori pe care le putem nota ca facând parte dintr-un nou vector, vectorul a, iar numărul de valori pe care îl avem este egal cu x = v[1]+v[2]+...+v[n].

Astfel, trebuie să aflați câte din cele 2x
submulțimi ale vectorului a au suma multiplu de n, modulo 109+7

==Date de intrare==
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, unde v[i] reprezintă numărul de valori egale cu i.

=Date de ieșire==
Programul va afișa pe ecran răspunsul cerut.

==Restricții și precizări==
1 ≤ n ≤ 100
cele n numere citite vor fi mai mici decât 200000
Pentru 20 de puncte, suma numerelor din vector nu va depăși 20.
Pentru 60 de puncte, suma numerelor din vector nu va depăși 100000.
==Exemplu==:
Intrare

3
1 1 1
Ieșire

4
==Exemplu== 2
Intrare

5
69 420 1017 128 953
Ieșire

985611225
==Rezolvare==
MOD = 10**9 + 7

def numar_submultimi(n, v):
# Inițializăm tabelul DP cu 0
DP = [[0] * n for _ in range(2)]

# Setăm valoarea inițială pentru submulțimile vide
DP[0][0] = 1

for i in range(1, n + 1):
# Trecem la o nouă matrice DP (pară/impară)
current = i % 2
previous = 1 - current

for j in range(n):
# Copiem valorile din matricea anterioară
DP[current][j] = DP[previous][j]

# Actualizăm matricea curentă adăugând valorile corespunzătoare din vector
DP[current][(j + i) % n] = (DP[current][(j + i) % n] + DP[previous][j]) % MOD

return DP[n % 2][0] - 1

if __name__ == "__main__":
# Citim datele de intrare
n = int(input())
v = list(map(int, input().split()))

# Calculăm rezultatul și afișăm rezultatul
rezultat = numar_submultimi(n, v)
print(rezultat)
python combatanti.py