0536 - Fabrica1

Cerinţa

La secția de împachetare a produselor dintr-o fabrică lucrează numar_muncitori muncitori. Fiecare muncitor împachetează același tip de produs, și pentru fiecare se cunoaște timpul necesar pentru împachetarea unui obiect. Să se determine durata minimă de timp în care vor împacheta cei numar_muncitori muncitori cel puțin numar_minim_obiecte obiecte.

Date de intrare

Programul citește de la tastatură numerele numar_muncitori și numar_minim_obiecte, iar apoi numar_muncitori numere naturale nenule, reprezentând timpul necesar fiecărui muncitor pentru împachetarea unui obiect.

Date de ieșire

Programul va afișa pe ecran numărul timp_muncitori, reprezentând numărul de unități de timp necesare pentru împachetarea celor numar_minim_obiecte obiecte. În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul " Datele de intrare nu corespund cerințelor impuse.".

Restricţii şi precizări

• 1 ⩽ numar_muncitori ⩽ 1000
• cele numar_muncitori numere citite vor fi mai mici decât 1000
• 1 ⩽ numar_minim_obiecte⩽ 1000000
• toate intervalele de timp sunt exprimate în aceeași unitate de măsură

Exemplu 1

Intrare

6 60
4 7 3 6 7 1

Ieșire

Datele de intrare corespund cerințelor impuse
30

Exemplu 2

Intrare

1200 2000000

Ieșire

Datele de intrare nu corespund cerințelor impuse

Rezolvare

def timp_minim_impachetare(numar_muncitori, numar_minim_obiecte, timp_muncitori):
    timp_minim = 0
    timp_maxim = max(timp_muncitori) * numar_minim_obiecte  # Limita superioară inițială pentru căutarea binară

    while timp_minim < timp_maxim:
        timp_mijlociu = (timp_minim + timp_maxim) // 2
        obiecte_impachetate = sum(timp_mijlociu // timp_muncitor for timp_muncitor in timp_muncitori)

        if obiecte_impachetate < numar_minim_obiecte:
            timp_minim = timp_mijlociu + 1
        else:
            timp_maxim = timp_mijlociu

    return timp_minim

if __name__ == "__main__":
    # Citirea datelor de intrare
    numar_muncitori, numar_minim_obiecte = map(int, input(
        "Introduceți numărul de muncitori și numărul minim de obiecte (n M): ").split())

    if not (1 <= numar_muncitori <= 1000 and 1 <= numar_minim_obiecte <= 1000000):
        print("Datele de intrare nu corespund cerințelor impuse")
        exit()

    timp_muncitori = list(
        map(int, input(f"Introduceți {numar_muncitori} timpi ai muncitorilor separați prin spațiu: ").split()))

    if any(not (1 <= timp_muncitor < 1000) for timp_muncitor in timp_muncitori):
        print("Datele de intrare nu corespund cerințelor impuse")
        exit()

    # Calculul timpului minim necesar
    rezultat = timp_minim_impachetare(numar_muncitori, numar_minim_obiecte, timp_muncitori)

    # Afișarea mesajului și rezultatului
    print("Datele de intrare corespund cerințelor impuse")
    print(f"Numărul minim de unități de timp necesare: {rezultat}")