Problem Statement
The prince has just been taught combinatorics at school. To ensure that the prince has been understanding things correctly, the king has given his son a really tough combinatorics problem to solve.
The problem is as follows:-
A string of 0's and 1's is called a good string iff the number of 00 blocks in the string is equal to the number of 11 blocks. It is possible that two consecutive 00 blocks have a common 0 and two consecutive 11 blocks have a common 1. For example, the number of 00 blocks in the string 1000100110000 is 6.
Given a string each of whose characters is either '0', '1' or '?', the prince needs to find the number of good strings which can be obtained by replacing each '?' by '0' or '1'.
The objective of the problem is to see whether the prince has understood combinatorics conceptually, and not his calculating capabilities. Hence, the king has asked him to give the answer modulo 1000000007.
You are given a String[] incomplete . Conatenate the elements of incomplete to get a single string. Your task is to help the prince by solving the above problem for this string.
The problem is as follows:-
A string of 0's and 1's is called a good string iff the number of 00 blocks in the string is equal to the number of 11 blocks. It is possible that two consecutive 00 blocks have a common 0 and two consecutive 11 blocks have a common 1. For example, the number of 00 blocks in the string 1000100110000 is 6.
Given a string each of whose characters is either '0', '1' or '?', the prince needs to find the number of good strings which can be obtained by replacing each '?' by '0' or '1'.
The objective of the problem is to see whether the prince has understood combinatorics conceptually, and not his calculating capabilities. Hence, the king has asked him to give the answer modulo 1000000007.
You are given a String[] incomplete . Conatenate the elements of incomplete to get a single string. Your task is to help the prince by solving the above problem for this string.
Definition
- Class:
- GoodStrings
- Method:
- howMany
- Parameters:
- String[]
- Returns:
- int
- Method signature:
- int howMany(String[] incomplete)
- (be sure your method is public)
Constraints
- incomplete will contain between 1 and 50 elements, inclusive.
- Each element of incomplete will contain between 1 and 50 characters, inclusive.
- Each character in incomplete will be one of '0', '1' and '?'.
Examples
No public sample cases were explicitly marked for this problem in the original data.
Back to all problems