DevuAndBeautifulSubstrings
2015 TCO 1C · 2015-04-08 · by praveen123
Problem Statement
Devu likes to play with binary strings: strings in which each character is either '0' or '1'.
Devu calls a binary string beautiful if it is nonempty and no two consecutive characters in the string are equal.. The beauty level of a binary string is the number of beautiful substrings it contains. For example, the beauty level of "0001" is 5. This string contains four beautiful substrings of length 1 and one beautiful substring of length 2.
You are given
Constraints
- n will be between 1 and 50, inclusive.
- cnt will be between 0 and n * (n + 1) / 2, inclusive.
2 2 Returns: 2
There are four binary strings of length 2: "00", "01", "10", and "11". Their beauty levels are 2, 3, 3, and 2, respectively. Hence, there are two binary strings of length 2 with beauty level 2.
2 1 Returns: 0
There is no binary string of length 2 with beauty level 1.
3 4 Returns: 4
15 35 Returns: 642
40 820 Returns: 2
Submissions are judged against all 134 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DevuAndBeautifulSubstrings with a public method long long countBeautifulSubstrings(int n, int cnt) · 134 test cases · 2 s / 256 MB per case