Problem Statement
The old witch is selling her apples at the local farmers' market. You don't speak her language.
The witch has B bins, numbered from 0 to B-1. There are exactly A apples in each of the bins. To your naked and untrained eye, all apples look the same.
You have overheard some locals who were speaking in a language you could understand. You have learned the following things:
- The witch has ordinary apples in some bins and poisoned apples in other bins.
- The poisoned apples cost more: ordinary ones cost 10 local coins a piece, poisoned ones cost 11. (Makes sense: you are paying for the poison as well.)
- There are at most P bins of poisoned apples.
You don't want to seem too suspicious so you want to make just a single purchase.
For the purchase you will bring B separate paper bags - one for each bin. You will select some number of apples from each bin and place them into the corresponding paper bag. When you are done shopping, the witch will take money from you corresponding to the total cost of the apples in your bags.
Can you make the purchase in such a way that you'll be absolutely sure which of the witch's bins contained poisoned apples and which ones have apples that are safe to eat? (Your only source of information is the total number of coins the witch took from you for the whole purchase.)
If the goal cannot be reached, return an empty
Definition
- Class:
- PoisonedApples
- Method:
- buy
- Parameters:
- int, int, int
- Returns:
- int[]
- Method signature:
- int[] buy(int B, int A, int P)
- (be sure your method is public)
Notes
- If multiple solutions exist, any valid solution will be accepted. In particular, it's not necessary to minimize the total cost of your purchase.
- Don't forget that you are physically unable to purchase more than A apples from any single bin.
- Assume you have enough coins to pay for any valid purchase of apples.
Constraints
- B will be between 1 and 8, inclusive.
- A will be between 1 and 1000, inclusive.
- P will be between 0 and B, inclusive.
Examples
5
10
0
Returns: {0, 0, 0, 0, 0 }
The witch has 5 bins with 10 apples in each of them. You already know that no bins are poisoned so there's no need to purchase anything.
2
1
2
Returns: { }
Two bins that have one apple each. Any subset of bins can be poisoned. You must buy both apples: if you don't, you won't know whether the bin(s) you left untouched are poisoned. But buying both apples does not work either. If the total is 21 coins, you can only deduce that there is exactly one poisoned bin but you cannot tell which one it is.
7
1000
1
Returns: {3, 1, 4, 2, 7, 5, 6 }
Seven large bins, at most one is poisoned. The example return value describes one valid purchase. For example, if the total cost of your purchase is 283 coins, you can be sure that bin #0 is the only poisoned bin.
4
1000
4
Returns: {1, 10, 100, 1000 }
This is a pretty convenient way to tell which subset of these bins is poisoned.
4
6
3
Returns: { }
1
1
0
Returns: {1 }
One bin, one apple. It's guaranteed not to be poisoned. We can leave it in the store, but we can also buy it and eat it. We chose to do the latter.
1
47
0
Returns: {0 }
1
1
1
Returns: {1 }
2
1
0
Returns: {0, 0 }
2
47
0
Returns: {0, 0 }
2
2
1
Returns: {1, 2 }
2
1
1
Returns: { }
2
2
2
Returns: {1, 2 }
2
1
2
Returns: { }
3
1
0
Returns: {0, 0, 0 }
3
47
0
Returns: {0, 0, 0 }
3
3
1
Returns: {1, 2, 3 }
3
2
1
Returns: { }
3
4
2
Returns: {1, 2, 4 }
3
3
2
Returns: { }
3
4
3
Returns: {1, 2, 4 }
3
3
3
Returns: { }
4
1
0
Returns: {0, 0, 0, 0 }
4
47
0
Returns: {0, 0, 0, 0 }
4
4
1
Returns: {1, 2, 3, 4 }
4
3
1
Returns: { }
4
7
2
Returns: {1, 2, 4, 7 }
4
6
2
Returns: { }
4
7
3
Returns: {3, 5, 6, 7 }
4
6
3
Returns: { }
4
7
4
Returns: {3, 5, 6, 7 }
4
6
4
Returns: { }
5
1
0
Returns: {0, 0, 0, 0, 0 }
5
47
0
Returns: {0, 0, 0, 0, 0 }
5
5
1
Returns: {1, 2, 3, 4, 5 }
5
4
1
Returns: { }
5
12
2
Returns: {1, 2, 4, 7, 12 }
5
11
2
Returns: { }
5
13
3
Returns: {3, 6, 11, 12, 13 }
5
12
3
Returns: { }
5
13
4
Returns: {3, 6, 11, 12, 13 }
5
12
4
Returns: { }
5
13
5
Returns: {3, 6, 11, 12, 13 }
5
12
5
Returns: { }
6
1
0
Returns: {0, 0, 0, 0, 0, 0 }
6
47
0
Returns: {0, 0, 0, 0, 0, 0 }
6
6
1
Returns: {1, 2, 3, 4, 5, 6 }
6
5
1
Returns: { }
6
18
2
Returns: {1, 2, 4, 8, 13, 18 }
6
17
2
Returns: { }
6
24
3
Returns: {3, 6, 12, 22, 23, 24 }
6
23
3
Returns: { }
6
24
4
Returns: {11, 17, 20, 22, 23, 24 }
6
23
4
Returns: { }
6
24
5
Returns: {11, 17, 20, 22, 23, 24 }
6
23
5
Returns: { }
6
24
6
Returns: {11, 17, 20, 22, 23, 24 }
6
23
6
Returns: { }
7
1
0
Returns: {0, 0, 0, 0, 0, 0, 0 }
7
47
0
Returns: {0, 0, 0, 0, 0, 0, 0 }
7
7
1
Returns: {1, 2, 3, 4, 5, 6, 7 }
7
6
1
Returns: { }
7
24
2
Returns: {1, 2, 4, 8, 14, 19, 24 }
7
23
2
Returns: { }
7
43
3
Returns: {3, 6, 12, 22, 41, 42, 43 }
7
42
3
Returns: { }
7
44
4
Returns: {20, 31, 37, 40, 42, 43, 44 }
7
43
4
Returns: { }
7
44
5
Returns: {20, 31, 37, 40, 42, 43, 44 }
7
43
5
Returns: { }
7
44
6
Returns: {20, 31, 37, 40, 42, 43, 44 }
7
43
6
Returns: { }
7
44
7
Returns: {20, 31, 37, 40, 42, 43, 44 }
7
43
7
Returns: { }
8
1
0
Returns: {0, 0, 0, 0, 0, 0, 0, 0 }
8
47
0
Returns: {0, 0, 0, 0, 0, 0, 0, 0 }
8
8
1
Returns: {1, 2, 3, 4, 5, 6, 7, 8 }
8
7
1
Returns: { }
8
34
2
Returns: {1, 2, 4, 8, 15, 24, 29, 34 }
8
33
2
Returns: { }
8
72
3
Returns: {6, 12, 23, 40, 68, 70, 71, 72 }
8
71
3
Returns: { }
8
84
4
Returns: {20, 40, 71, 77, 80, 82, 83, 84 }
8
83
4
Returns: { }
8
84
5
Returns: {20, 40, 71, 77, 80, 82, 83, 84 }
8
83
5
Returns: { }
8
84
6
Returns: {20, 40, 71, 77, 80, 82, 83, 84 }
8
83
6
Returns: { }
8
84
7
Returns: {20, 40, 71, 77, 80, 82, 83, 84 }
8
83
7
Returns: { }
8
84
8
Returns: {20, 40, 71, 77, 80, 82, 83, 84 }
8
83
8
Returns: { }
4
147
2
Returns: {1, 2, 4, 7 }
This return value works for P = 2 but it would not be valid for P = 3. E.g., in the P = 3 case if the purchase cost 147 coins, it would be possible that bins 0+1+2 are poisoned but it would also be possible that only bin 3 is poisoned.
8
100
4
Returns: {20, 40, 71, 77, 80, 82, 83, 84 }
8
92
3
Returns: {6, 12, 23, 40, 68, 70, 71, 72 }
8
38
2
Returns: {1, 2, 4, 8, 15, 24, 29, 34 }
8
85
8
Returns: {20, 40, 71, 77, 80, 82, 83, 84 }
6
25
6
Returns: {11, 17, 20, 22, 23, 24 }
8
100
8
Returns: {20, 40, 71, 77, 80, 82, 83, 84 }
8
120
2
Returns: {1, 2, 4, 8, 15, 24, 29, 34 }
8
80
3
Returns: {6, 12, 23, 40, 68, 70, 71, 72 }