Nộp bài
Điểm:
1700 (thành phần)
Thời gian:
0.25s
Scratch
8.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, bf, C, C++, Haskell, Java, javascript, NASM, Pascal, Perl, scratch, text
Đây là một phiên bản khó hơn của bài toán trong sách giáo khoa. Statement được chép nguyên văn từ sách.
Hồng có n file dữ liệu được đánh số từ 0 đến n - 1 và có kích thước tương ứng là s_0, s_1, ..., s_{n - 1} (Mb). Hồng muốn tìm cách lưu trữ nhiều file dữ liệu nhất bằng hai đĩa ổ cứng, mỗi ổ có dung lượng d (Mb). Bạn hãy lập trình giúp Hồng giải quyết bài toán.
Input, Output và Subtask
Input (bàn phím
)
- Dòng đầu tiên gồm hai số nguyên dương n, d (n, d \le 1000).
- Dòng tiếp theo gồm n số nguyên dương s_i (s_i \le 1000).
Output (màn hình
)
- Một dòng duy nhất gồm số lượng file dữ liệu lớn nhất có thể lưu trữ được.
Spoiler
- May cho các bạn là mình không yêu cầu các bạn truy vết .
Subtask
Tỉ lệ điểm (%) | Giới hạn |
---|---|
40 | n \le 10 |
30 | n \le 16 |
20 | n, d, s_i \le 128 |
10 | Không có giới hạn gì thêm |
Sample 1
Input (bàn phím
)
5 8
1 2 3 4 5
Output (màn hình
)
5
Notes
- Ta có thể lưu các file 1, 2, 5 vào đĩa 1 và 3, 4 vào đĩa 2.
Sample 2
Input (bàn phím
)
5 10
4 5 6 7 5
Output (màn hình
)
4
Bình luận