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
Definition
- Class:
- DevuAndBeautifulSubstrings
- Method:
- countBeautifulSubstrings
- Parameters:
- int, int
- Returns:
- long
- Method signature:
- long countBeautifulSubstrings(int n, int cnt)
- (be sure your method is public)
Constraints
- n will be between 1 and 50, inclusive.
- cnt will be between 0 and n * (n + 1) / 2, inclusive.
Examples
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
50
94
Returns: 32357325751902
1
0
Returns: 0
1
1
Returns: 2
2
0
Returns: 0
2
1
Returns: 0
2
2
Returns: 2
2
3
Returns: 2
3
0
Returns: 0
3
1
Returns: 0
3
2
Returns: 0
3
3
Returns: 2
3
4
Returns: 4
3
5
Returns: 0
3
6
Returns: 2
50
114
Returns: 11702340820662
50
697
Returns: 4080
50
881
Returns: 120
50
1211
Returns: 0
50
844
Returns: 48
50
600
Returns: 23424
50
1249
Returns: 0
50
1121
Returns: 0
50
123
Returns: 6112844691130
50
790
Returns: 48
49
1047
Returns: 0
49
1072
Returns: 0
49
351
Returns: 16468878
49
987
Returns: 0
49
859
Returns: 0
49
494
Returns: 413568
49
767
Returns: 108
49
709
Returns: 144
49
1011
Returns: 0
49
882
Returns: 12
44
62
Returns: 70552643202
47
71
Returns: 1517606097672
43
85
Returns: 235736203608
46
155
Returns: 17909350386
47
140
Returns: 125325724122
43
91
Returns: 168151379926
50
68
Returns: 1014068076524
43
69
Returns: 206737586850
42
109
Returns: 18006203328
46
163
Returns: 10269094988
44
86
Returns: 486259569590
47
155
Returns: 42511148992
46
143
Returns: 42132742866
44
82
Returns: 552904213284
49
190
Returns: 25111043444
45
132
Returns: 40069738172
47
128
Returns: 312711092862
50
93
Returns: 32910768777764
49
187
Returns: 29932241848
50
146
Returns: 1092802455310
48
96
Returns: 6798263258824
46
119
Returns: 264900322248
49
77
Returns: 8862853544598
49
81
Returns: 13269771945790
50
113
Returns: 12531251617894
48
140
Returns: 299217500616
47
147
Returns: 74998267002
49
152
Returns: 296890702074
46
117
Returns: 309608181790
47
95
Returns: 3275480162930
43
126
Returns: 11043317034
49
197
Returns: 16214631972
43
85
Returns: 235736203608
44
122
Returns: 36352306268
48
118
Returns: 1606517633804
46
85
Returns: 2181828009154
47
108
Returns: 1443815758118
40
65
Returns: 30839036520
42
115
Returns: 11035087484
50
88
Returns: 32710109848602
49
82
Returns: 14174298118770
50
103
Returns: 23082314773038
49
96
Returns: 14604429192108
49
78
Returns: 10037041082054
50
95
Returns: 31655612945468
17
32
Returns: 6450
26
117
Returns: 4620
22
77
Returns: 3516
36
320
Returns: 3108
24
109
Returns: 2064
21
81
Returns: 1104
25
105
Returns: 4338
24
118
Returns: 1196
40
451
Returns: 1764
31
229
Returns: 1312
44
580
Returns: 1200
35
283
Returns: 1896
41
460
Returns: 1140
14
72
Returns: 4
7
12
Returns: 6
32
528
Returns: 2
5
15
Returns: 2
45
45
Returns: 2
8
23
Returns: 6
7
18
Returns: 4
11
47
Returns: 6
17
111
Returns: 4
11
66
Returns: 2
39
556
Returns: 4
38
633
Returns: 8
6
6
Returns: 2
34
502
Returns: 4
5
15
Returns: 2
12
46
Returns: 4
19
115
Returns: 0
43
20
Returns: 0
38
666
Returns: 0
30
438
Returns: 0
13
9
Returns: 0
8
0
Returns: 0
50
1010
Returns: 0
46
36
Returns: 0
26
290
Returns: 0
29
428
Returns: 0
40
606
Returns: 0
32
415
Returns: 0
29
414
Returns: 0
11
63
Returns: 0
46
41
Returns: 0
46
1051
Returns: 0
22
174
Returns: 0
46
1051
Returns: 0
50
1234
Returns: 0
50
1100
Returns: 0
50
150
Returns: 817735475708