2772 - Placinte

Placinte

Nimic nu se compară cu plăcintele calde ieșite din cuporul bunicii! Alexa simte mirosul ispititor al bunătățurilor proaspete și coboară în bucătărie ca să descopere n tipuri diferite de plăcinte. Unele sunt cu mere, altele cu vișine, altele cu brânză, în fine! Bunica ei a făcut câte o infinitate din fiecare tip. Dacă fata alege să mănânce un tip de plăcintă, ea îl mănâncă numai sub forma unui set. Un set de plăcinte de tipul i este egal cu 2i−1

. Fata cunoaște din experiență timpul Ti necesar pentru a mânca un set de plăcinte de tip i.

Cerința

Ș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 ieșire

Programul va afișa pe ecran un singur număr, timplul minim necesar pentru a mânca cel puțin k plăcinte.

Restricții și precizări

• 1≤n≤30
• 1≤k,Ti≤109

Exemple

Intrare

4 11

2 3 4 5

Ieșire

9

Î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.

…sau:

Intrare

2 5

1 3

Ieșire

5

…sau:

Intrare

5 1000000000

32145 1421431 13124 315125 124124

Ieșire

3281000000000

Rezolvare:

def validare_date(n, k, Ti):
    # Verifică condițiile de validare
    if not (1 <= n <= 30):
        return False, "Numărul de tipuri de plăcinte trebuie să fie între 1 și 30."

    if not (1 <= k <= 10 ** 9):
        return False, "Numărul minim de plăcinte de consumat trebuie să fie între 1 și 10^9."

    if not all(1 <= timp <= 10 ** 9 for timp in Ti):
        return False, "Toate timpurile trebuie să fie între 1 și 10^9."

    return True, None

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

# Validare date
valid, mesaj_eroare = validare_date(n, k, Ti)

if valid:
    timp_minim = timp_minim_placinte(Ti, n, k)
    print(timp_minim)
else:
    print("Datele introduse nu sunt valide. Motiv:", mesaj_eroare)