2772 - Placinte

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]

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