TopCoder problem "LotteryTicket" used in SRM 466 (Division II Level One)



Problem Statement

    Nick likes to play the lottery. The cost of a single lottery ticket is price. Nick has exactly four banknotes with values b1, b2, b3 and b4 (some of the values may be equal). He wants to know if it's possible to buy a single lottery ticket without getting any change back. In other words, he wants to pay the exact price of a ticket using any subset of his banknotes. Return "POSSIBLE" if it is possible or "IMPOSSIBLE" if it is not (all quotes for clarity).
 

Definition

    
Class:LotteryTicket
Method:buy
Parameters:int, int, int, int, int
Returns:String
Method signature:String buy(int price, int b1, int b2, int b3, int b4)
(be sure your method is public)
    
 

Constraints

-price will be between 1 and 4000, inclusive.
-b1, b2, b3 and b4 will each be between 1 and 1000, inclusive.
 

Examples

0)
    
10
1
5
10
50
Returns: "POSSIBLE"
Nick can use the banknote with value b3.
1)
    
15
1
5
10
50
Returns: "POSSIBLE"
Here he can use the banknotes with values b2 and b3.
2)
    
65
1
5
10
50
Returns: "POSSIBLE"
b2 + b3 + b4 is 65.
3)
    
66
1
5
10
50
Returns: "POSSIBLE"
All four banknotes must be used.
4)
    
1000
999
998
997
996
Returns: "IMPOSSIBLE"
5)
    
20
5
5
5
5
Returns: "POSSIBLE"
Some of the banknote values may be equal.
6)
    
2
1
5
10
50
Returns: "IMPOSSIBLE"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10860

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14150&pm=10860

Writer:

Chmel_Tolstiy

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Brute Force, Recursion