Bò trong tòa nhà chọc trời

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò cần đi từ tầng trên xuống tầng trệt bằng thang máy. Thang máy có sức chứa tối đa $W$ kg. Con bò thứ $i$ nặng $C_{i}$ kg. Mỗi lần thang máy chỉ có thể chở các con bò với tổng trọng lượng $\leq W$ .

Tìm số chuyến thang máy ít nhất để đưa tất cả bò xuống.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ và $W$ .
$N$ dòng tiếp: Trọng lượng $C_{i}$ của con bò thứ $i$ .

Dữ liệu ra

Một số nguyên — số chuyến thang máy ít nhất.

Ràng buộc

$1 \leq N \leq 18$
$1 \leq C_{i} \leq W \leq 10^{8}$

Ví dụ

Input	Output	Giải thích
4 10 5 6 3 7	3	Chuyến 1: bò 1+3 (5+3=8≤10), chuyến 2: bò 2 (6≤10), chuyến 3: bò 4 (7≤10).

Bình luận

Không có bình luận tại thời điểm này.