ORGAN - VNOI

ORGAN - VOI 2013 - Sản xuất đồ chơi

Giới hạn

Thời gian: 2.0s
Bộ nhớ: 1536MB
Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Xưởng sản xuất đồ chơi XYZ đã mua các lô hàng ống đàn để làm nguyên liệu sản xuất đàn ống. Mỗi lô gồm n (n > 2) ống đàn với độ cao đôi một khác nhau lần lượt là h ₁ , h ₂ , ..., h _n để khi nhạc công gõ vào các ống đàn với độ cao khác nhau, ống sẽ phát ra các âm thanh khác nhau. Ống đàn thứ i có trọng lượng là h _i x m (1 ≤ i ≤ n). Quy trình sản xuất đàn của hãng thực hiện theo dây chuyền tự đông hoàn toàn như sau: Bắt đầu, robot A sẽ tự động mở một lô và xếp lần lượt n ống có độ cao h ₁ , h ₂ , ..., h _n lên dây chuyền. Tiếp theo, các ống sẽ được robot B phân thành s (1 < s ≤ n) lô con. Lô con thứ nhất gồm các ống từ 1 đến k ₁ , lô con thứ hai gồm các ống từ k ₁ + 1 đến k ₂ , ..., lô con thứ s gồm các ống từ k _s-1 + 1 đến n (1 ≤ k ₁ < k ₂ < ... < k _s-1 < n). Mỗi một lô con sẽ được chuyển cho robot C để lắp thành một chiếc đàn. Robot C sẽ tiến hành sắp xếp các ống thành một dãy đảm bảo điều kiện có không quá w vị trí ống đứng trước cao hơn ống đứng liền kề sau nó (nếu có). Có thể có nhiều phương án sắp xếp các ống đàn trong một lô con thỏa mãn điều kiện này. Mỗi một phương án như vậy sẽ được gọi là một loại đàn. Sau khi khảo sát thị hiếu người tiêu dùng, Ban giám đốc nhận thấy: trọng lượng hợp lý của một chiếc đàn (được tính bởi tổng trọng lượng của các ống đàn) là một số không nhỏ hơn b _min và không lớn hơn b _max ; ngoài ra, không có hai khách hàng nào lại muốn dùng đàn giống nhau. Dễ thấy, số lượng loại đàn khác nhau có thể tạo ra phụ thuộc vào việc n ống thành s lô con. Do đó, Ban giám đốc muốn lựa chọn cách phân n ống thành s lô con sao cho tổng trọng lượng các ống trong mỗi lô con đều nằm trong đoạn từ b _min đến b _max và số lượng các loại đàn ống khác nhau có thể sản xuất được là nhiều nhất.

Ví dụ

Với n = 5; s = 2; w = 2; m = 1; b _min = 9; b _max = 12 và dãy các ống có độ cao là 4, 6, 2, 3, 7 có 2 cách phân 5 ống thành 2 lô con:

Cách phân lô thứ nhất: Lô con 1 gồm các ống với các trọng lượng tương ứng là 4, 6, 2. Lô con 2 gồm các ống với các trọng lượng tương ứng là 3, 7.

Lô con thứ nhất có thể sản xuất các loại đàn:

Số lượng loại đàn không có vị trí nào mà ống đứng trước cao hơn ống đứng liền kề sau nó là 1 (2-4-6);
Số lượng loại đàn có đúng 1 vị trí mà ống đứng trước cao hơn ống đứng liền kề sau nó là 4 (2-6-4, 4-2-6, 4-6-2, 6-2-4);
Số lượng loại đàn có đúng 2 vị trí mà ống đứng trước cao hơn ống liền kề sau nó là 1 (6-4-2);

Do đó, từ các ống trong lô con thứ nhất có thể sản xuất 6 loại đàn.
Từ các ống trong lô con thứ hai có thể sản xuất thêm 2 loại đàn mới (3-7, 7-3).
Vậy, theo các phân lô thứ nhất có thể sản xuất 8 loại đàn.

Cách phân lô thứ hai: Lô con 1 gồm các ống với các trọng lượng tương ứng là 4, 6. Lô con 2 gồm các ống với các trọng lượng tương ứng là 2, 3, 7. Tính tương tự như trên, cách phân lô này cho phép sản xuất 8 loại đàn.

Vậy đáp số cần tìm là 8.

Yêu cầu

Hãy tìm cách phân n ống thành s lô con thỏa mãn các điều kiện đặt ra và sao cho số lượng loại đàn ống khác nhau có thể sản xuất được là nhiều nhất.

Dữ liệu

Dòng đầu tiên chứa T (T<=10) là số lượng bộ dữ liệu. Tiếp đến là T nhóm dòng, mỗi nhóm dòng cho thông tin về một bộ dữ liệu theo khuôn dạng sau:

Dòng thứ nhất chứa sáu số nguyên dương n, s, w, m, b _min , b _max .
Dòng thứ hai gồm n số nguyên dương h ₁ , h ₂ , ..., h _n mô tả độ cao của n ống.

Giới hạn : m < 100; b _min , b _max < 10 ⁹ ; h _i < 10 ⁶ . Dữ liệu bảo đảm bài toán có lời giải.

Kết quả

Gồm T dòng, mỗi dòng chứa một số nguyên là số lượng các loại đàn khác nhau tìm được tương ứng với bộ dữ liệu vào.

Test ví dụ

Input:
1
5 2 2 1 9 12
4 6 2 3 7

Output:
8

Ràng buộc

Có 30% số test ứng với 30% số điểm của bài có n ≤ 10.
Có 30% số test ứng với 30% số điểm của bài có 10 < n ≤ 30.
Có 40% số test ứng với 40% số điểm của bài có 30 < n ≤ 200.

Người up: voj
Nguồn bài: VOI 2013 - Ngày 2