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.|

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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/organ


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à h1, h2, ..., hn để 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à hi 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 h1, h2, ..., hn 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 k1, lô con thứ hai gồm các ống từ k1 + 1 đến k2, ..., lô con thứ s gồm các ống từ ks-1 + 1 đến n (1 ≤ k1 < k2 < ... < ks-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 bmin và không lớn hơn bmax; 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ừ bmin đến bmax 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; bmin = 9; bmax = 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, bmin, bmax.
  • Dòng thứ hai gồm n số nguyên dương h1, h2, ..., hn mô tả độ cao của n ống.

Giới hạn : m < 100; bmin, bmax < 109; hi < 106. 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.

Được gửi lên bởi:VOJ Team
Ngày:2013-01-12
Thời gian chạy:2s
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:VOI 2013 - Ngày 2

hide comments
2017-11-27 15:07:36
thiếu writeln làm 100 xún 10 -.-
2017-08-09 19:29:03
xem code và công thức QHD: https://vietcodes.github.io/code/35
2016-01-30 08:06:29
tham khao http://codevnspoj.blogspot.com/
2013-11-22 15:41:15 Thủ khoa vãn
code mai van duoc co 90 ko biet sai cho nao
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.