Back to Category
d247: [12.08] C - RFC 1149

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 0 Times | Submit :3 Times | Clicks : 396
Accepted : 0 Users | Submit : 1 Users | Accepted rate : 0%
Time Limit :1000 ms | Memory Limit : 64000 KBytes
Update : 2012-11-01 19:39


Company X in country Y wants to do a remote backup for its large volume of data. Since in country Y, the network bandwidth is low and cost is high, so using network to transmit data could take years and its cost is unacceptable. So, their engineers decide to follow RFC 1149 (IP over Avian Carriers): they copy the data into hard disks and then mail them by air to the remote site.
Unfortunately, their engineers only have some obselete, old hard disks at their disposal. The volumes of these hard disks are not always the same. To simplify their problems, they divide the hard disks in batches. In each batch, all hard disks have the same volume. The air mail is done by one batch. In order to save the shipping fee, they need to use the space of hard disks as much as possible, because shipping fee is charged by weight. One more hard disk in a batch means more cost.
Given a set of files and a set of hard disks with the same volume, please find a way to allocate the files so that the shipping fee is minimum.

Technical Specifications

  • The number of test cases would be smaller than or equal to 20.
  • The number files to be allocated would be smaller than or equal to 50. 


The test data begins with an integer N which is the number of test cases. Each test case determines a mailing package for a batch. A test case begins with an integer V (10 < V < 10000), which is the volume of hard disks for the batch. Please assume the hard disks of volume V can always be provided until all the files are allocated. Following is an integer M, which is the number of files to be allocated in the batch. The second line of a test
case is a list of integers xi separated by spaces. Each integer ( 0 < xi < V, 1 ≤ i ≤ M ) represents the file sizes to be copied. 


For each test case (a.k.a., a batch), please output the used disk space size for each hard disk. If more than one hard disk is needed, please output the sizes of all hard disks in descending order.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3200 16
989 375 1090 22 1560 238 1004 1532 1489 737 1986 925 116 917 931 203
8272 16
1915 5072 3610 2144 3361 2065 2946 3651 3494 187 3824 4236 4486 920 275 4102

Sample Output :

3200 3200 3200 3049 1465
8269 8255 8181 8060 8018 5505

Hint :

click here to download the problem solving hint

Author :

  Solve it!   Status Forum


Program running time may be affected by various factors. Check server system environment information here