TIEROPE - Tie the Rope
Sailor Crow'n-beard has many pieces of rope. Every piece has a different value and it is well known that money equals quality. Crow'n-beard wants you to create a program that given pieces of rope, creates a rope with the length as close as possible to his desired length (but never too short) while maximizing the quality.
Input
Input describes a single test case. The first line contains two integers N (1 ≤ N ≤ 80) and L (1 ≤ L ≤ 10000): the number of rope pieces Crow'n-beard and the desired length respectively. Then N lines will follow, each with two integers: the length Li (0 ≤ Li < 2^31) followed by the value Vi (0 ≤ Vi ≤ 26843545) of the piece of rope. It is guaranteed that the sum of Li is never less than L.
Output
You should output the maximal total quality you can reach. Remember that the priority is to get the smallest total length that is still at least equal to L. Only then output the best total quality amongst equal length solutions.
Sample
Input: 4 4 20 2 1 4 3 4 4 7 Output: 8
hide comments
|
hello_world123:
2018-07-03 19:27:39
Awesome problem !!!
|
|
Riddhi:
2016-02-13 05:30:36
The sum of lengths of ropes is <=10^6 |
|
Mitch Schwartz:
2013-09-10 01:47:16
As the problem setter is not responding, I've updated the problem description, adding important info and cleaning up in general. The constraints are a little silly because I don't want to waste my time finding out sharper constraints by experimentation. And I removed the sentence "All of them are worthless, but when tied together they can form a useful rope" because it could be interpreted to mean that a solution has to use at least two pieces of rope, when in fact there is no such requirement. Last edit: 2013-09-10 02:00:16 |
|
(Tjandra Satria Gunawan)(曾毅昆):
2013-08-24 20:45:01
@Mitch Schwartz: Thanks for your experiment :-)
|
|
Laurens:
2013-08-14 17:42:31
@Kevin the answer would be 4. Since length 6 cannot be made, the first length that can is 7, and for 7 the optimal value is 4. |
|
Kevin Sebastian:
2013-08-14 04:28:29
please explain for example if I have three ropes of length 2,3,5 and values 1,2,3 and desired length 6 then what would the answer be? |
|
|
Mitch Schwartz:
2013-08-12 17:56:27
@maradona: If you have two pieces of rope with lengths 2 and 3, and the desired length is 4, then you will end up exceeding it and taking 5. |
|
maradona:
2013-08-12 17:56:27
How it's possible exceed the desired length?
|
|
|
Mitch Schwartz:
2013-08-12 17:56:27
Please give constraints for the length and value of a piece of rope.
|
|
|
Laurens:
2013-08-12 17:56:27
@Mitch, the latter. @raunak see Mitch question, it also applies to your submission after i took a quick glance at your code. |
| Added by: | Laurens |
| Date: | 2013-08-11 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Own problem |
RSS