Hàng đợi tại trạm xe buýt

Điểm: 2,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

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

Tại trạm xe buýt có $n$ nhóm người đứng xếp hàng. Nhóm thứ $i$ (tính từ đầu hàng) có $a_{i}$ người. Cứ mỗi $30$ phút, một chiếc xe buýt rỗng đến trạm và có thể chở tối đa $m$ người.

Hành khách lên xe theo thứ tự nhóm: nhóm đầu hàng lên trước, rồi đến nhóm thứ hai, và cứ thế. Thứ tự các nhóm trong hàng không bao giờ thay đổi. Một quy tắc quan trọng: nếu chiếc xe hiện tại không thể chở toàn bộ thành viên của một nhóm, thì cả nhóm đó sẽ chờ chuyến xe tiếp theo, và tất cả các nhóm xếp sau cũng phải chờ cùng.

Hãy xác định cần bao nhiêu chuyến xe buýt để chở hết tất cả $n$ nhóm.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra một số nguyên duy nhất — số chuyến xe buýt cần thiết.

Ràng buộc

$1 \leq n, m \leq 100$
$1 \leq a_{i} \leq m$

Ví dụ

Input	Output	Giải thích
3 4 1 2 1	1	Tổng số người là $1 + 2 + 1 = 4$ , vừa đúng sức chứa của một chuyến xe.
4 3 2 3 2 1	3	Chuyến 1 chở nhóm đầu ( $2$ người), nhóm hai ( $3$ người) không vừa nên đi chuyến 2. Chuyến 3 chở nhóm ba ( $2$ ) và nhóm bốn ( $1$ ).

Bình luận

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