4029 - Depozit - Revision history

Benzar Ioan: /* Rezolvare */

2024-06-03T01:51:33Z

Rezolvare

← Older revision		Revision as of 01:51, 3 June 2024
Line 15:		Line 15:

	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line="1">
	MOD = 1_000_000_007		MOD = 1_000_000_007

Line 52:		Line 52:
	def main():		def main():
	N = int(input().strip())		N = int(input().strip())
	assert 1 <= N <= ~~10000007~~, "N nu este in parametru"		assert 1 <= N <= 1000000000, "N nu este in parametru"
	max_stive, num_cuts = calculate_stive_and_cuts(N)		max_stive, num_cuts = calculate_stive_and_cuts(N)
	print(max_stive+1, num_cuts+1)		print(max_stive+1, num_cuts+1)

Benzar Ioan at 01:50, 3 June 2024

2024-06-03T01:50:56Z

← Older revision		Revision as of 01:50, 3 June 2024
Line 1:		Line 1:
	== Cerința ==		== Cerința ==
	Într-un depozit, ~~managerul dorește~~ să ~~organizeze mărfurile în diverse combinații pe rafturi~~. ~~Fiecare raft~~ poate ~~conține 1, 2 sau 3 unități de marfă~~. ~~Să se determine în câte moduri diferite poate managerul~~ să ~~aranjeze mărfurile pe rafturi pentru a avea un total~~ de ~~n unități~~ de ~~marfă~~.		Într-un depozit au fost așezate cutii identice, una după alta, eventual suprapuse, astfel încât numărul maxim de cutii suprapuse într-o stivă este N, iar între două stive cu același număr de cutii să existe cel puțin una cu mai multe cutii decât oricare dintre cele două. Considerăm că o stivă poate fi formată dintr-o singură cutie.
			Proprietarul depozitului vă cere să aflați numărul maxim de stive care pot construi respectând regulile date și numărul de cutii care pot fi aranjate astfel. Pentru că numerele pot fi foarte mari rezultatele se vor afișa modulo 1.000.000.007.
	== Date de intrare ==		== Date de intrare ==
	Programul citește de la tastatură ~~un număr întreg n reprezentând numărul total de unități de marfă pe care managerul dorește să le aranjeze pe rafturi~~.		Programul citește de la tastatură N.
	== Date de ieșire ==		== Date de ieșire ==
	Pe ecran ~~se va afișa~~ numărul de ~~moduri diferite în~~ care ~~managerul poate aranja mărfurile pe rafturi pentru a avea un total~~ de ~~n unități de marfă~~.		Programul afișează pe ecran numărul maxim de stive care pot construi și numărul de cutii care pot fi aranjate modulo 1.000.000.007.
	== Restricții și precizări ==		== Restricții și precizări ==
	*1 ~~&les; '''n''' &les; 30~~		*1 ≤ N ≤ 1.000.000.000
	== Exemplu 1 ==		== Exemplu 1 ==
	;Intrare		;Intrare
	4		3
	;Iesire		;Iesire
	7		7 11

	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	~~def citeste_date():~~		MOD = 1_000_000_007
	~~try:~~
	n = ~~int(input("Introduceți numărul total de unități de marfă (n): "))~~
	~~return n~~
	~~except ValueError:~~
	~~return None~~

	~~def valideaza_date(n):~~
	~~return 1 <= n <= 30~~

	def ~~numara_moduri~~(n):		def factorial(n, mod):
	if n ~~== 0~~:		result = 1
			for i in range(2, n + 1):
			result = (result * i) % mod
			return result


			def mod_inverse(x, mod):
			return pow(x, mod - 2, mod)


			def comb(n, k, mod):
			if k > n:
	return 0		return 0
	~~elif~~ n =~~= 1:~~		num = factorial(n, mod)
	return 1		denom = (factorial(k, mod) * factorial(n - k, mod)) % mod
	~~elif n == 2~~:		return (num * mod_inverse(denom, mod)) % mod
	~~return~~ 2
	~~elif n~~ =~~= 3:~~
	~~return 4~~		def calculate_stive_and_cuts(N):
			# Numărul maxim de stive este (N + 1) * N // 2
			max_stive = (N + 1) * N // 2

	moduri ~~= [0] * (n + 1)~~		# Numărul de moduri de a aranja cutiile
	~~moduri[0]~~ = 1		num_cuts = 1
	~~moduri[1] =~~ 1		for i in range(1, N):
	~~moduri[2]~~ = 2		num_cuts = (num_cuts * (2 * N - i) * mod_inverse(i, MOD)) % MOD
	~~moduri[3] = 4~~

	~~for i in range(4~~, ~~n + 1):~~		return max_stive, num_cuts
	~~moduri[i] = moduri[i - 1] + moduri[i - 2] + moduri[i - 3]~~

	~~return moduri[n]~~

	def main():		def main():
	n = ~~citeste_date~~()		N = int(input().strip())
			assert 1 <= N <= 10000007, "N nu este in parametru"
	~~if n is None or not valideaza_date~~(n):		max_stive, num_cuts = calculate_stive_and_cuts(N)
	~~print("Datele de intrare nu corespund restricțiilor impuse."~~)		print(max_stive+1, num_cuts+1)
	~~return~~

	~~print(~~"~~Datele de intrare corespund restricțiilor impuse.~~")
	~~moduri~~ = ~~numara_moduri~~(n)
	print(~~moduri~~)

	if __name__ == "__main__":		if __name__ == "__main__":
	main()		main()


	</syntaxhighlight>		</syntaxhighlight>

Benzar Ioan: Pagină nouă: == Cerința == Într-un depozit, managerul dorește să organizeze mărfurile în diverse combinații pe rafturi. Fiecare raft poate conține 1, 2 sau 3 unități de marfă. Să se determine în câte moduri diferite poate managerul să aranjeze mărfurile pe rafturi pentru a avea un total de n unități de marfă. == Date de intrare == Programul citește de la tastatură un număr întreg n reprezentând numărul total de unități de marfă pe care managerul dorește să le...

2024-06-02T19:41:25Z

Pagină nouă: == Cerința == Într-un depozit, managerul dorește să organizeze mărfurile în diverse combinații pe rafturi. Fiecare raft poate conține 1, 2 sau 3 unități de marfă. Să se determine în câte moduri diferite poate managerul să aranjeze mărfurile pe rafturi pentru a avea un total de n unități de marfă. == Date de intrare == Programul citește de la tastatură un număr întreg n reprezentând numărul total de unități de marfă pe care managerul dorește să le...

New page

== Cerința ==
Într-un depozit, managerul dorește să organizeze mărfurile în diverse combinații pe rafturi. Fiecare raft poate conține 1, 2 sau 3 unități de marfă. Să se determine în câte moduri diferite poate managerul să aranjeze mărfurile pe rafturi pentru a avea un total de n unități de marfă.
== Date de intrare ==
Programul citește de la tastatură un număr întreg n reprezentând numărul total de unități de marfă pe care managerul dorește să le aranjeze pe rafturi.
== Date de ieșire ==
Pe ecran se va afișa numărul de moduri diferite în care managerul poate aranja mărfurile pe rafturi pentru a avea un total de n unități de marfă.
== Restricții și precizări ==
*1 &les; '''n''' &les; 30
== Exemplu 1 ==
;Intrare
4
;Iesire
7

== Rezolvare ==
<syntaxhighlight lang="python" line>
def citeste_date():
try:
n = int(input("Introduceți numărul total de unități de marfă (n): "))
return n
except ValueError:
return None

def valideaza_date(n):
return 1 <= n <= 30

def numara_moduri(n):
if n == 0:
return 0
elif n == 1:
return 1
elif n == 2:
return 2
elif n == 3:
return 4

moduri = [0] * (n + 1)
moduri[0] = 1
moduri[1] = 1
moduri[2] = 2
moduri[3] = 4

for i in range(4, n + 1):
moduri[i] = moduri[i - 1] + moduri[i - 2] + moduri[i - 3]

return moduri[n]

def main():
n = citeste_date()

if n is None or not valideaza_date(n):
print("Datele de intrare nu corespund restricțiilor impuse.")
return

print("Datele de intrare corespund restricțiilor impuse.")
moduri = numara_moduri(n)
print(moduri)

if __name__ == "__main__":
main()

</syntaxhighlight>