Editing 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: ==
<syntaxhighlight lang="python">
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)
</syntaxhighlight>