Connection Status:
Competition Arena > BagsOfMarbles

BagsOfMarbles

SRM 771 · 2019-11-26 · by misof

SRM 771 · 2019-11-26 · by misof · Greedy, Simple Math, Simple Search, Iteration
Class Name: BagsOfMarbles
Return Type: int
Method Name: removeFewest
Arg Types: (int, int, int, int, int, int)
Problem Statement

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.

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
0)
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.

1)
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.

2)
51
7
7
7
7
7
Returns: 63
3)
7
10
7
0
0
0
Returns: -1
4)
7
10
0
7
0
0
Returns: 7

Submissions are judged against all 89 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BagsOfMarbles with a public method int removeFewest(int desired, int bagSize, int noWhiteBags, int noBlackBags, int someWhiteBags, int someBlackBags) · 89 test cases · 2 s / 256 MB per case

Submitting as anonymous