PCAKES

Points: 100

Time limit: 1.0s

Memory limit: 493M

Problem type

Trong nhà bếp của Bin có \(n\) con gà, con gà thứ \(i\) cứ sau khoảng thời gian \(t_i\) giây sẽ đẻ ra 1 quả trứng.

Yêu cầu: tính thời gian tối thiểu để Bin nướng được \(X\) chiếc bánh, biết rằng 1 chiếc bánh chỉ sử dụng 1 quả trứng.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(X (0 < X < 10^{15})\) và \(n (0 < n < 20) \)
Dòng thứ hai chứa \(n\) số nguyên dương, số thứ \(i\) là thời gian \(t_i\) tương ứng sau khoảng thời gian \(t_i\) con gà thứ \(i\) lại đẻ quả trứng. \((t_i < 500)\)

Dữ liệu ra

Một số duy nhất là thời gian tối thiểu để nướng \(X\) chiếc bánh.

Sample Input

3 2
50 70

Sample Output

Comments

K36_khanh commented on May 31, 2025, 10:27 p.m.

include <iostream>

include <algorithm>

include <climits>

using namespace std;

bool isPossible(long long time, long long X, int n, int times[]) { long long total = 0; for (int i = 0; i < n; i++) { total += time / times[i]; // Tránh tràn số và dừng sớm khi đủ if (total >= X || total < 0) return true; } return total >= X; }

long long findMinTime(long long X, int n, int times[]) { if (n == 0) return 0;

long long left = 0;
// Tính right an toàn hơn, tránh tràn số
long long max_time = *max_element(times, times + n);
long long right = 1;
while (right <= X && right <= LLONG_MAX / max_time) {
    right *= 2;
}
right = min(right, LLONG_MAX / max_time) * max_time;

long long result = right;

while (left <= right) {
    long long mid = left + (right - left) / 2;
    if (isPossible(mid, X, n, times)) {
        result = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}
return result;

}

int main() { long long X; int n; cin >> X >> n;

if (X <= 0 || n <= 0 || n >= 20) {
    cout << 0 << endl;
    return 0;
}

int times[20];
for (int i = 0; i < n; i++) {
    cin >> times[i];
    if (times[i] <= 0 || times[i] >= 500) {
        cout << 0 << endl;
        return 0;
    }
}

cout << findMinTime(X, n, times) << endl;
return 0;

} chatgpt tài trợ chương trình