Python Basic Contest #01 - Lưu trữ dữ liệu (Python only)

Điểm: 1700 (thành phần)

Thời gian: 1.5s

Bộ nhớ: 512M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Ngôn ngữ cho phép

~~NASM~~, Python

Đâ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)

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)

Bình luận

Không có bình luận nào.