Editing 2963 - Mostenire 1 (section)

== Rezolvare ==
<syntaxhighlight lang="python" line>
def citire_date():
    with open("mostenire.in", "r") as f:
        N, K = map(int, f.readline().split())
        saci = [int(f.readline().strip()) for _ in range(N)]
    return N, K, saci

def verifica_parametrii(N, K, saci):
    assert 2 <= K <= 100, "Numarul de feciori trebuie sa fie intre 2 si 100"
    assert K <= N <= 100000, "Numarul de saci trebuie sa fie intre numarul de feciori si 100000"
    assert all(1 <= galbeni <= 100000 for galbeni in saci), "Numarul de galbeni din fiecare sac trebuie sa fie intre 1 si 100000"
    assert sum(saci) <= 1000000000, "Numarul total de galbeni trebuie sa fie cel mult 1.000.000.000"

def poate_primi_mezinul(saci, suma_mezin, K):
    suma_curenta = 0
    numar_fii = 0
    for galbeni in saci:
        if suma_curenta + galbeni > suma_mezin:
            numar_fii += 1
            suma_curenta = 0
            if numar_fii == K:
                return False
        suma_curenta += galbeni
    return numar_fii < K

def gaseste_suma_maxima(saci, K):
    suma_totala = sum(saci)
    stanga, dreapta = 0, suma_totala
    while stanga < dreapta:
        mijloc = (stanga + dreapta + 1) // 2
        if poate_primi_mezinul(saci, mijloc, K):
            stanga = mijloc
        else:
            dreapta = mijloc - 1
    return stanga

def determina_impartire(saci, suma_mezin, K):
    impartire = []
    suma_curenta = 0
    saci_curenti = 0
    fii_chemati = []

    for i in range(len(saci)):
        if suma_curenta + saci[i] > suma_mezin and len(fii_chemati) < K - 1:
            impartire.append((len(fii_chemati) + 1, saci_curenti))
            fii_chemati.append(len(fii_chemati) + 1)
            saci_curenti = 0
            suma_curenta = 0
        suma_curenta += saci[i]
        saci_curenti += 1

    impartire.append((K, saci_curenti))
    return impartire

def scrie_rezultate(suma_mezin, impartire):
    with open("mostenire.out", "w") as f:
        f.write(f"{suma_mezin}\n")
        for ord_fiu, numar_saci in impartire:
            f.write(f"{ord_fiu} {numar_saci}\n")

def impartire_saci():
    N, K, saci = citire_date()
    verifica_parametrii(N, K, saci)
    suma_mezin = gaseste_suma_maxima(saci, K)
    impartire = determina_impartire(saci, suma_mezin, K)
    scrie_rezultate(suma_mezin, impartire)

if __name__ == "__main__":
    impartire_saci()

</syntaxhighlight>