Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BINPACK - Binpacking

Một xí nghiệp có một robot dùng để xếp các sản phẩm vào các thùng. Mọi thùng đều có dung tích như nhau. Có đúng hai thùng đang mở sẵn để robot xếp các sản phẩm vào. Mỗi thùng bất kỳ đều chứa được số sản phẩm mà tổng dung tích của chúng không vượt quá dung tích của thùng. Robot có thể thực hiện các thao tác sau:

  1. Đưa một sản phẩm hiện tại trên dãy băng vào thùng 1.
  2. Đưa một sản phẩm hiện tại trên dãy băng vào thùng 2.
  3. Đóng thùng 1 và mở một thùng mới thay thế cho thùng 1.
  4. Đóng thùng 2 và mở một thùng mới thay thế cho thùng 2.

Các thao tác 1, 2 chỉ có thể thực hiện nếu tổng dung tích của sản phẩm cho vào và các sản phẩm đã có trong thùng không vượt quá dung tích của thùng.

 

Yêu cầu: Cho biết dung tích mỗi thùng là L, dung tích của N sản phẩm trên dãy băng theo thứ tự xuất hiện là a1, a2,..., aN , hãy tìm số thùng ít nhất để có thể cho N sản phẩm vào thùng.

Input

  • Dòng thứ nhất là hai số nguyên dương L và N
  • Dòng tiếp theo chứa các số mô tả các số a1, a2, …,aN (1 ≤ ai ≤ L)

Output

  • Gồm 1 số duy nhất là số thùng ít nhất cần dùng

Example

Input:

8 6
4 2 5 3 5 4

Output: 3

Subtask 1 : (5 test - 1s / 1 test)

L ≤ 109 và N ≤ 20

Subtask 2 : (5 test - 2s / 1 test)

1 ≤ ai ≤ 2; L = 100 và N ≤ 106

Subtask 3 : (5 test - 3s / 1 test)

L ≤ 30 và N ≤ 10000

Subtask 4 : (5 test - 3s / 1 test)

L ≤ 5000 và N ≤ 100

Subtask 5 : (5 test - 4s / 1 test)

L ≤ 5000 và N ≤ 10000


Được gửi lên bởi:Quan To
Ngày:2011-10-06
Thời gian chạy:0.200s-0.800s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Thầy Đỗ Đức Đông

hide comments
2019-10-19 12:50:00
http://eunsetee.com/Y5An
2019-07-08 02:10:03
cho em xin solution với ạ
2017-11-18 02:47:26
nhật hào sạch
2016-09-27 03:14:52
Code AC:
http://shink.in/ASVwZ
2016-03-04 10:40:58 even when you try to hurt me...
bài thầy đông.....
2016-01-30 11:38:20
tham khảo : http://codevnspoj.blogspot.com/
2014-12-07 16:32:09 Lollipop
các thùng bỏ vào từng hộp là theo thứ tự cửa băng chuyền hay là bỏ lộn xộn vậy
2011-10-16 12:28:17 Ðỗ Việt Anh
1 2 2 2 2 1
Với 1 là thao tác cho vào thùng 1, 2 là thùng 2 -> 3 thùng mang 3 giá trị (7;8;8)
2011-10-13 15:09:01 rock
bạn nào giải thích test vd giúp mình, mình nghõ ra 4 chứ.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.