Problem Statement
You want to have desired white marbles. Currently you have none. All the marbles are in bags owned by your friend. Each of your friend's bags contains exactly bagSize marbles. Each of those marbles is either white (you want those) or black (you don't care about those).
Your friends has bags of four types:
- Red bags are guaranteed to have no white marbles inside. There are noWhiteBags such bags.
- Green bags are guaranteed to have no black marbles inside. There are noBlackBags such bags.
- Blue bags are guaranteed to have some white marbles inside. There are someWhiteBags such bags.
- Fuchsia bags are guaranteed to have some black marbles inside. There are someBlackBags such bags.
You are going to take marbles from your friend's bags, one at a time. More precisely, in each step you may choose any specific bag owned by your friend and take one random marble from that bag.
Return the smallest X such that you can be sure to reach your goal after taking X marbles (provided that you choose the bags in a smart way). If it's impossible to give such a guarantee, return -1 instead.
Definition
- Class:
- BagsOfMarbles
- Method:
- removeFewest
- Parameters:
- int, int, int, int, int, int
- Returns:
- int
- Method signature:
- int removeFewest(int desired, int bagSize, int noWhiteBags, int noBlackBags, int someWhiteBags, int someBlackBags)
- (be sure your method is public)
Notes
- The statements "a bag contains no white marbles" and "a bag contains some white marbles" are opposites. I.e., a bag contains some white marbles if and only if it is not true that it contains no white marbles.
Constraints
- desired will be between 1 and 40,000, inclusive.
- bagSize will be between 1 and 100, inclusive.
- noWhiteBags will be between 0 and 100, inclusive.
- noBlackBags will be between 0 and 100, inclusive.
- someWhiteBags will be between 0 and 100, inclusive.
- someBlackBags will be between 0 and 100, inclusive.
Examples
5
10
0
1
0
0
Returns: 5
We want 5 white marbles. Each bag contains 10 marbles. Our friend has 1 bag that contains no black marbles. The optimal stragegy is clear: take any five marbles from that bag.
2
10
2
0
1
0
Returns: -1
We want 2 white marbles. Each bag contains 10 marbles. Our friend has three bags: 2 that contain no white marbles, and 1 that contains some white marbles. We cannot be sure that there is a way to get two white marbles -- given what we know, it is possible that there only one white ball exists.
51
7
7
7
7
7
Returns: 63
7
10
7
0
0
0
Returns: -1
7
10
0
7
0
0
Returns: 7
7
10
0
0
7
0
Returns: 70
7
10
0
0
0
7
Returns: -1
7
10
6
0
0
0
Returns: -1
7
10
0
6
0
0
Returns: 7
7
10
0
0
6
0
Returns: -1
7
10
0
0
0
6
Returns: -1
7
1
100
5
5
100
Returns: 7
7
1
100
4
4
100
Returns: 7
7
1
100
3
3
100
Returns: -1
10100
100
100
100
100
100
Returns: 20000
10101
100
100
100
100
100
Returns: -1
361
9
71
74
33
51
Returns: 361
631
6
85
0
0
93
Returns: -1
560
2
73
30
0
57
Returns: -1
981
31
0
92
77
72
Returns: 981
589
98
0
0
13
75
Returns: -1
393
66
13
0
28
96
Returns: -1
113
99
78
87
99
0
Returns: 113
945
34
69
0
73
34
Returns: -1
968
94
0
0
0
33
Returns: -1
986
78
0
0
0
66
Returns: -1
833
80
56
98
0
83
Returns: 833
624
67
91
3
0
56
Returns: -1
982
89
0
26
0
0
Returns: 982
804
73
68
14
57
0
Returns: 804
126
54
0
0
0
0
Returns: -1
524
63
0
68
73
0
Returns: 524
76
23
0
82
0
0
Returns: 76
63
49
0
0
0
31
Returns: -1
628
94
0
80
0
44
Returns: 628
570
7
0
46
73
77
Returns: -1
144
9
0
3
73
0
Returns: -1
803
91
65
0
0
22
Returns: -1
474
3
0
59
82
0
Returns: -1
194
87
6
70
50
0
Returns: 194
805
14
69
75
53
0
Returns: 805
648
12
0
52
69
14
Returns: 912
836
12
47
0
0
33
Returns: -1
216
38
0
57
41
0
Returns: 216
595
62
0
59
79
38
Returns: 595
105
39
0
44
55
0
Returns: 105
584
66
41
0
77
79
Returns: -1
572
23
6
0
0
0
Returns: -1
421
8
0
0
1
0
Returns: -1
75
72
1
64
81
94
Returns: 75
126
66
14
0
71
0
Returns: -1
180
86
61
77
0
56
Returns: 180
767
26
51
0
43
0
Returns: -1
498
12
4
80
0
0
Returns: 498
660
27
92
65
0
0
Returns: 660
737
23
90
0
1
78
Returns: -1
241
81
14
9
0
0
Returns: 241
865
24
0
0
0
0
Returns: -1
604
51
16
38
0
99
Returns: 604
93
83
14
0
0
0
Returns: -1
788
92
65
67
82
56
Returns: 788
693
53
3
0
0
13
Returns: -1
450
99
0
56
0
0
Returns: 450
419
61
89
0
0
0
Returns: -1
506
42
0
0
10
0
Returns: -1
858
78
6
0
25
0
Returns: -1
51
7
7
7
1
7
Returns: -1
51
7
7
7
1
1
Returns: -1
1
1
0
0
0
1
Returns: -1
5
2
0
2
0
2
Returns: -1
2
10
2
0
1
5
Returns: -1
100
20
0
0
0
100
Returns: -1
100
1
1
1
1
11
Returns: -1
1
10
5
0
0
5
Returns: -1
51
7
7
7
7
8
Returns: 63
51
7
7
7
0
5
Returns: -1
1
1
0
0
1
0
Returns: 1
10
1
12
5
1
10
Returns: -1
2
10
2
0
1
1
Returns: -1
62
10
0
5
2
10
Returns: -1
5
5
0
0
0
5
Returns: -1
2
2
0
0
0
2
Returns: -1
51
7
7
7
3
7
Returns: 63
10
3
0
3
1
9
Returns: 12
51
7
7
7
0
7
Returns: -1
6
5
0
1
3
0
Returns: 10
1
2
0
0
1
0
Returns: 2
3
1
1
1
1
1
Returns: -1
10
1
0
0
0
90
Returns: -1