Cerința

La secția de împachetare a produselor dintr-o fabrică lucrează n 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 n muncitori cel puțin M obiecte.

Date de intrare

Programul citește de la tastatură numerele n și M, iar apoi n 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 T, reprezentând numărul de unități de timp necesare pentru împachetarea celor M obiecte.

Restricții și precizări

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

Exemplu

Intrare

6 60
4 7 3 6 7 1 

Ieșire

30

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, prod;
    cin >> n >> prod;
    int a[1001];
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    int st = 1, dr = 1000000, min = 1000001;
    while(st <= dr){
        int mij = (st + dr) / 2;
        int val = 0;
        for(int i = 1; i <= n; ++i)
            val += mij / a[i];
        if(val >= prod){
            if(mij < min)
                min = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }

    cout << min;

    return 0;
}