Connection Status:
Competition Arena > BitStrings

BitStrings

SRM 248 · 2005-06-21 · by NeverMore

SRM 248 · 2005-06-21 · by NeverMore · Dynamic Programming
Class Name: BitStrings
Return Type: int
Method Name: maxStrings
Arg Types: (vector<string>, int, int)
Problem Statement

Problem Statement

You are given a list of bitstrings (i.e. strings consisting of only 0's and 1's). You also have a number of 0's and 1's at your disposal. You want to know the maximum number of bitstrings in the list that you can create using those 0's and 1's. Of course, once you use a zero or one, you cannot use it again.

Create a class BitStrings that contains a method maxStrings. maxStrings takes a String[] list, an int numZeroes and an int numOnes as input. The method should return the maximum number of strings from list that can be created using numZeroes zeroes and numOnes ones. Again, reusing zeroes and ones is not allowed.

Constraints

  • list will contain between 2 and 20 elements inclusive.
  • Each element of list will have a length between 1 and 50 inclusive.
  • Each element of list will contain only the characters '0' and '1'.
  • numZeroes and numOnes will each be between 0 and 500 inclusive.
Examples
0)
{"1", "00", "100"}
3
1
Returns: 2

Here, you have three 0's and one 1 at your disposal. The best you can do is create the first two bitstrings. Note that if you create the third bitstring, then you cannot construct any other bitstrings because you won't have a sufficient number of 0's and 1's.

1)
{"00", "110", "101"}
2
4
Returns: 2

In this case, you have 2 0's and 4 1's. Although you can make the first bitstring "00", you then run out of zeroes and cannot make any more; in this case, you can only construct 1 bitstring. You can do better if you leave the first bitstring and construct the last two, giving a final answer of 2.

2)
{"111", "01", "11", "10", "101"}
3
9
Returns: 5
3)
{"00", "000", "00000"}
0
100
Returns: 0
4)
{"110", "01", "1101", "00"}
2
3
Returns: 2

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

Coding Area

Language: C++17 · define a public class BitStrings with a public method int maxStrings(vector<string> list, int numZeroes, int numOnes) · 47 test cases · 2 s / 256 MB per case

Submitting as anonymous