All submissions for this problem are available.
Munnabhai needs a curtain rod of length L. He already has curtain rods of certain lengths but all are smaller than L. Munnabhai is a frugal man. He decides that if its possible to make a rod of length L by joining the smaller rods, he won't buy a new one. So firstly, given a set of rods, Munnabhai needs to determine whether he can make a rod of length L by joining the available rods(NOTE: If n rods of lengths l1,l2,...,ln are joined together, we get a rod of length l1+l2+...+ln). If this can be done, then he will choose a set of rods such that:
1.) There are minimum number of joints in the final rod of length L.
2.) Munnabhai's store-room is designed in a way that its infinitely more difficult to keep one larger rod as compared to any number of smaller rods. So he chooses the set accordingly.
(Example: For L=25, 10,10,5 is preferred over 10,9,6 because keeping(in the store or not using) a rod of length 10 is infinitely more difficult than keeping rods of lengths 9 and 6 together.)
Munnabhai gives greater priority to criteria (1) as compared to (2).
L n l1 p1 l2 p2 . . . . . . ln pn
where, L is the final rod length
n is the number of rod lengths available
l(i) is available rod-length 1<=i<=n
p(i) is the number of rods available of rod-length l(i) 1<=i<=n
L,n,l1,l2,...,ln,p1,p2,...,pn are all positive integers
l1*p1 + l2*p2 + ... + ln*pn < 999
M l1 q1 l2 q2 . . . . . . ln qn
where, M is the minimum number of rods needed
l(i) is available rod-length, 1<=i<=n
q(i) is the number of rods of rod-length l(i) used, 1<=i<=n
If it is not possible to make a rod of length L from the given set of rods, then
Not possible to make a rod of length L from the given set of rods
25 4 10 2 9 1 6 1 5 1
3 10 2 9 0 6 0 5 1
25 3 10 1 9 1 5 1
Not possible to make a rod of length 25 from the given set of rods
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, GO, NODEJS, BF|
Fetching successful submissions
If you are still having problems, see a sample solution here.