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]

# 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)