Hi,

1. If any product is mentioned in the list then the minimum weight of that product should be at least 1. So, if you have input like this

3
a 1 1000
b 0
c 0

Then the minimum total weight of this scenario is 1002 because b and c got to have at least 1. The maximum is 3000. The final answer is NO.

2. Multiple products can have same weights so for the above case the max total weight is 3000 with a = b = c = 1000.

The problem can be solved by finding the minimum possible weight and maximum possible weight and checking if 10000 is in between them. For example:

3
a 0
b 0
c 1 5

The minimum possible weight is 15 (a = b = c = 5) and the maximum possible weight is 20005 (a = b = 10000 and c = 5). And so 15 <= 10000 <= 20005 and hence the answer is true. Well the real answer is a = 4998, b = 4997 and c = 5. You just need to run two loops, one for finding minimum weight and the another one for finding maximum weight.

And here some test cases from other places on this forum:

Test Case 1

4
Water 0
Cocoa-butter 0
Cocoa-powder 1 4000
Lecithin 0

Minimum Sum is 12001 and maximum sum is 28000 so the answer is NO.

Test Case 2

5
a1 1 2001
a2 0
a3 0
a4 0
a5 1 1999

Minimum sum is 9997 and the maximum sum is 10003 and so the answer is YES.

Test Case 3

4
w 1 10
a 0
b 1 1
c 0

Minimum sum is 13 and the maximum sum is 22 so the answer is NO.

Test Case 4

3
a 1 3
b 0
c 0

Minimum sum is 5 and the maximum sum is 9 so the answer is NO.

Test Case 5

3
a 1 10000
b 0
c 0

Minimum sum is 10002 and the maximum sum is 30000 so the answer is NO.

Test Case 6

3
a 0
b 0
c 0

Minimum sum is 3 and the maximum sum is 30000 so the answer is YES

Test Case 7

5
a1 1 9997
a2 0
a3 0
a4 0
a5 0

Minimum sum is 10001 and the maximum sum is 49985 so the answer is NO.

Varun

Edited by author 24.12.2010 08:51

Thanks! =)