LotteryTicket
SRM 466 · 2009-11-12 · by Chmel_Tolstiy
SRM 466 · 2009-11-12 · by Chmel_Tolstiy · Brute Force, Recursion
Problem Statement
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).
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.
Submissions are judged against all 192 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LotteryTicket with a public method string buy(int price, int b1, int b2, int b3, int b4) · 192 test cases · 2 s / 256 MB per case