0730 - Minus K - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:30:51Z

Rezolvare

← Older revision		Revision as of 18:30, 11 January 2024
Line 22:		Line 22:
	Cele 8 şiruri sunt: ++++, +++-, ++-+, +-++, -+++, +-+-, -++-, -+-+. În niciunul dintre aceste şiruri nu avem două sau mai mult de două caractere – pe poziţii consecutive.		Cele 8 şiruri sunt: ++++, +++-, ++-+, +-++, -+++, +-+-, -++-, -+-+. În niciunul dintre aceste şiruri nu avem două sau mai mult de două caractere – pe poziţii consecutive.
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	MOD = 2011		MOD = 2011

Mraa at 17:36, 11 January 2024

2024-01-11T17:36:55Z

← Older revision		Revision as of 17:36, 11 January 2024
Line 22:		Line 22:
	Cele 8 şiruri sunt: ++++, +++-, ++-+, +-++, -+++, +-+-, -++-, -+-+. În niciunul dintre aceste şiruri nu avem două sau mai mult de două caractere – pe poziţii consecutive.		Cele 8 şiruri sunt: ++++, +++-, ++-+, +-++, -+++, +-+-, -++-, -+-+. În niciunul dintre aceste şiruri nu avem două sau mai mult de două caractere – pe poziţii consecutive.
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	MOD = 2011		MOD = 2011

	def numar_siruri(N, K):		def numar_siruri(N, K):
	~~# Inițializăm matricea dp cu 0-uri~~
	~~dp = [[0] * 2 for _ in range(N + 1)]~~

	# Prima coloană este 1, pentru că există un singur șir de lungime 0, și anume șirul vid		# Inițializăm matricea dp cu 0-uri
	dp[0][0] = 1		dp = [[0] * 2 for _ in range(N + 1)]
			# Prima coloană este 1, pentru că există un singur șir de lungime 0, și anume șirul vid
	# Calculăm numărul de șiruri		dp[0][0] = 1
	for i in range(1, N + 1):		# Calculăm numărul de șiruri
	# Dacă adăugăm + în șirul anterior, nu adăugăm un semn - pe poziția i		for i in range(1, N + 1):
	dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD		# Dacă adăugăm + în șirul anterior, nu adăugăm un semn - pe poziția i
	# Dacă adăugăm - în șirul anterior, verificăm dacă am adăugat deja K semne - consecutive		dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
	if i >= K:		# Dacă adăugăm - în șirul anterior, verificăm dacă am adăugat deja K semne - consecutive
	dp[i][1] = (dp[i - 1][0] - dp[i - K][1] + MOD) % MOD		if i >= K:
	else:		dp[i][1] = (dp[i - 1][0] - dp[i - K][1] + MOD) % MOD
	dp[i][1] = dp[i - 1][0]		else:
			dp[i][1] = dp[i - 1][0]
	return (dp[N][0] + dp[N][1]) % MOD		return (dp[N][0] + dp[N][1]) % MOD

	if __name__ == "__main__":		if __name__ == "__main__":
	~~with open("minusk.in", "r") as f:~~
	~~N, K = map(int, f.readline().split())~~

	~~rezultat = numar_siruri(N, K)~~

	with open("minusk.out", "w") as g:		with open("minusk.in", "r") as f:
	g.write(str(rezultat) + "\n")		N, K = map(int, f.readline().split())
	~~python minusk.py~~		rezultat = numar_siruri(N, K)
			with open("minusk.out", "w") as g:
			g.write(str(rezultat) + "\n")
			</syntaxhighlight>

Mraa: Pagină nouă: ==Cerința== Se dau două numere naturale N şi K. Determinaţi numărul de şiruri de lungime N formate doar din semnele + şi – şi în care nu apar K semne – pe poziţii consecutive. ==Date de intrare== Fișierul de intrare minusk.in conţine pe prima linie 2 numere naturale separate printr-un spaţiu, N şi K, cu semnificaţia din enunţ. ==Date de ieșire== Fișierul de ieșire minusk.out va conține pe prima linie un singur număr natural reprezentând valoarea ce...

2023-12-21T21:10:37Z

Pagină nouă: ==Cerința== Se dau două numere naturale N şi K. Determinaţi numărul de şiruri de lungime N formate doar din semnele + şi – şi în care nu apar K semne – pe poziţii consecutive. ==Date de intrare== Fișierul de intrare minusk.in conţine pe prima linie 2 numere naturale separate printr-un spaţiu, N şi K, cu semnificaţia din enunţ. ==Date de ieșire== Fișierul de ieșire minusk.out va conține pe prima linie un singur număr natural reprezentând valoarea ce...

New page

==Cerința==
Se dau două numere naturale N şi K. Determinaţi numărul de şiruri de lungime N formate doar din semnele + şi – şi în care nu apar K semne – pe poziţii consecutive.

==Date de intrare==
Fișierul de intrare minusk.in conţine pe prima linie 2 numere naturale separate printr-un spaţiu, N şi K, cu semnificaţia din enunţ.

==Date de ieșire==
Fișierul de ieșire minusk.out va conține pe prima linie un singur număr natural reprezentând valoarea cerută, modulo 2011.

==Restricții și precizări==
1 ≤ K ≤ N ≤ 1000000;
pentru 30% dintre teste N ≤ 10
pentru 70% dintre teste N ≤ 1000
==Exemplu==:
minusk.in

4 2
minusk.out

8
==Explicație==
Cele 8 şiruri sunt: ++++, +++-, ++-+, +-++, -+++, +-+-, -++-, -+-+. În niciunul dintre aceste şiruri nu avem două sau mai mult de două caractere – pe poziţii consecutive.
==Rezolvare==
MOD = 2011

def numar_siruri(N, K):
# Inițializăm matricea dp cu 0-uri
dp = [[0] * 2 for _ in range(N + 1)]

# Prima coloană este 1, pentru că există un singur șir de lungime 0, și anume șirul vid
dp[0][0] = 1

# Calculăm numărul de șiruri
for i in range(1, N + 1):
# Dacă adăugăm + în șirul anterior, nu adăugăm un semn - pe poziția i
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
# Dacă adăugăm - în șirul anterior, verificăm dacă am adăugat deja K semne - consecutive
if i >= K:
dp[i][1] = (dp[i - 1][0] - dp[i - K][1] + MOD) % MOD
else:
dp[i][1] = dp[i - 1][0]

return (dp[N][0] + dp[N][1]) % MOD

if __name__ == "__main__":
with open("minusk.in", "r") as f:
N, K = map(int, f.readline().split())

rezultat = numar_siruri(N, K)

with open("minusk.out", "w") as g:
g.write(str(rezultat) + "\n")
python minusk.py