[Buổi 14][Chuyên đề Tham lam & chiến lược tìm kiếm][WS] Bài 1: Giá trị nhỏ nhất chưa thể tạo
Giá trị nhỏ nhất chưa thể tạo
Bối cảnh và bài toán
Có n token dương; mỗi token dùng tối đa một lần. Cần tìm số nguyên dương nhỏ nhất không thể biểu diễn thành tổng của một tập con token.
Yêu cầu
In giá trị nhỏ nhất không tạo được.
Input
- Dòng 1:
n. - Dòng 2:
ngiá trị dương.
Output
In số nguyên dương nhỏ nhất không thể tạo.
Ràng buộc
1 <= n <= 2 * 10^51 <= x[i] <= 10^9
Chấm điểm
| Subtask | Điểm | Điều kiện | Official tests |
|---|---|---|---|
| S1 | 20% | n ≤ 500 | 01–04 |
| S2 | 30% | n ≤ 5 * 10^4 | 05–10 |
| S3 | 50% | Không có ràng buộc bổ sung | 11–20 |
Ví dụ 1
Input
5
2 9 1 2 7
Output
6
Giải thích. Tạo được mọi tổng 1..5, nhưng không tạo được 6.
Ví dụ 2
Input
1
2
Output
1
Giải thích. Không có token giá trị 1 nên 1 là đáp án.
Thông tin bài tập
| Thuộc tính | Giá trị |
|---|---|
| Mã bài | DSA-M04-B14-WS01 |
| Buổi | B14 |
| Loại bài | WORKSHOP |
| Mức độ khó | Trung bình (Medium) |
| Thời gian làm bài khuyến nghị | 50 phút |
| Time limit | 2 giây |
| Memory limit | 256 MB |
| Tổng điểm | 100 |
| Chuẩn ngôn ngữ tham chiếu | C++11 trở lên |
| Yêu cầu bổ sung | Decision Note |
Nguồn: Phỏng theo CSES Problem Set — Missing Coin Sum (Task 2183).
Tham khảo: https://cses.fi/problemset/task/2183
Comments