2772 - Placinte - Revision history

Andrada378 at 12:55, 5 January 2024

2024-01-05T12:55:53Z

@@ Line 1: / Line 1: @@
-Cerinta:
+== Placinte ==
 Știind că fata va mânca fără preferințe câte seturi de plăcinte va vrea din fiecare tip, să se calculeze timpul minim necesar pentru a mânca cel puțin k plăcinte.
-Date de iesire:
+== Date de intrare ==
 Programul va afișa pe ecran un singur număr, timplul minim necesar pentru a mânca cel puțin k plăcinte.
-Rezolvare:
+== Restricții și precizări ==
-   def timp_minim_placinte(Ti, n, k):
-     dp = [float('inf')] * (k + 1)
+* 1≤n≤30
-     dp[0] = 0
+* 1≤k,Ti≤109
-     for i in range(1, k + 1):
+== Exemple ==
-         for j in range(n):
+'''Intrare'''
-             if i >= 2 ** j:
-                 dp[i] = min(dp[i], dp[i - 2 ** j] + (2 ** j) * Ti[j])
+11
-     return dp[k]
+3 4 5
- # Citirea datelor de la tastatură
+'''Ieșire'''
- n = int(input("Introdu numărul de tipuri de plăcinte: "))
- k = int(input("Introdu numărul minim de plăcinte de consumat: "))
- Ti = list(map(int, input("Introdu timpurile necesare pentru fiecare tip de plăcinte: ").split()))
+În acest exemplu, este mai avantajos să mănânce un set de plăcinte de tip 4 (adică 8 plăcinte) și un set de tip 3 (4 plăcinte), consumând în total 12 plăcinte în 9 unități de timp. Ar putea să mănânce 11 plăcinte sub forma 1 + 2 + 8, dar ar dura 10 unități de timp.
- timp_minim = timp_minim_placinte(Ti, n, k)
- print(timp_minim)
+…sau:

Andrada378 at 18:22, 13 December 2023

2023-12-13T18:22:15Z

← Older revision		Revision as of 18:22, 13 December 2023
Line 2:		Line 2:
	Știind că fata va mânca fără preferințe câte seturi de plăcinte va vrea din fiecare tip, să se calculeze timpul minim necesar pentru a mânca cel puțin k plăcinte.		Știind că fata va mânca fără preferințe câte seturi de plăcinte va vrea din fiecare tip, să se calculeze timpul minim necesar pentru a mânca cel puțin k plăcinte.
	Date de intrare:		Date de intrare:
	Programul citește de la tastatură numerele n, k și apoi n numere, reprezentând timpurile T1,T2,…,Tn		Programul citește de la tastatură numerele n, k și apoi n numere, reprezentând timpurile T1,T2,…,Tn necesare pentru a mânca un set din fiecare tip de plăcintă (în ordine, tipurile 1, 2, …, n).
	necesare pentru a mânca un set din fiecare tip de plăcintă (în ordine, tipurile 1, 2, …, n).
	Date de iesire:		Date de iesire:
	Programul va afișa pe ecran un singur număr, timplul minim necesar pentru a mânca cel puțin k plăcinte.		Programul va afișa pe ecran un singur număr, timplul minim necesar pentru a mânca cel puțin k plăcinte.

	Rezolvare:		Rezolvare:
	def timp_minim_placinte(Ti, n, k):		def timp_minim_placinte(Ti, n, k):
	dp = [float('inf')] * (k + 1)		dp = [float('inf')] * (k + 1)
	dp[0] = 0		dp[0] = 0

	for i in range(1, k + 1):		for i in range(1, k + 1):
	for j in range(n):		for j in range(n):
	if i >= 2 ** j:		if i >= 2 ** j:
	dp[i] = min(dp[i], dp[i - 2 j] + (2 j) * Ti[j])		dp[i] = min(dp[i], dp[i - 2 j] + (2 j) * Ti[j])

	return dp[k]		return dp[k]

	# Citirea datelor de la tastatură		# Citirea datelor de la tastatură
	n = int(input("Introdu numărul de tipuri de plăcinte: "))		n = int(input("Introdu numărul de tipuri de plăcinte: "))
	k = int(input("Introdu numărul minim de plăcinte de consumat: "))		k = int(input("Introdu numărul minim de plăcinte de consumat: "))
	Ti = list(map(int, input("Introdu timpurile necesare pentru fiecare tip de plăcinte: ").split()))		Ti = list(map(int, input("Introdu timpurile necesare pentru fiecare tip de plăcinte: ").split()))

	timp_minim = timp_minim_placinte(Ti, n, k)		timp_minim = timp_minim_placinte(Ti, n, k)
	print(timp_minim)		print(timp_minim)

Andrada378: Pagină nouă: Cerinta: Știind că fata va mânca fără preferințe câte seturi de plăcinte va vrea din fiecare tip, să se calculeze timpul minim necesar pentru a mânca cel puțin k plăcinte. Date de intrare: Programul citește de la tastatură numerele n, k și apoi n numere, reprezentând timpurile T1,T2,…,Tn necesare pentru a mânca un set din fiecare tip de plăcintă (în ordine, tipurile 1, 2, …, n). Date de iesire: Programul va afișa pe ecran un singur număr, timplul mi...

2023-12-13T18:20:58Z

Pagină nouă: Cerinta: Știind că fata va mânca fără preferințe câte seturi de plăcinte va vrea din fiecare tip, să se calculeze timpul minim necesar pentru a mânca cel puțin k plăcinte. Date de intrare: Programul citește de la tastatură numerele n, k și apoi n numere, reprezentând timpurile T1,T2,…,Tn necesare pentru a mânca un set din fiecare tip de plăcintă (în ordine, tipurile 1, 2, …, n). Date de iesire: Programul va afișa pe ecran un singur număr, timplul mi...

New page

Cerinta:
Știind că fata va mânca fără preferințe câte seturi de plăcinte va vrea din fiecare tip, să se calculeze timpul minim necesar pentru a mânca cel puțin k plăcinte.
Date de intrare:
Programul citește de la tastatură numerele n, k și apoi n numere, reprezentând timpurile T1,T2,…,Tn
necesare pentru a mânca un set din fiecare tip de plăcintă (în ordine, tipurile 1, 2, …, n).
Date de iesire:
Programul va afișa pe ecran un singur număr, timplul minim necesar pentru a mânca cel puțin k plăcinte.
Rezolvare:
def timp_minim_placinte(Ti, n, k):
dp = [float('inf')] * (k + 1)
dp[0] = 0

for i in range(1, k + 1):
for j in range(n):
if i >= 2 ** j:
dp[i] = min(dp[i], dp[i - 2 ** j] + (2 ** j) * Ti[j])

return dp[k]

# Citirea datelor de la tastatură
n = int(input("Introdu numărul de tipuri de plăcinte: "))
k = int(input("Introdu numărul minim de plăcinte de consumat: "))
Ti = list(map(int, input("Introdu timpurile necesare pentru fiecare tip de plăcinte: ").split()))

timp_minim = timp_minim_placinte(Ti, n, k)
print(timp_minim)