ForbiddenStrings
SRM 412 · 2008-07-30 · by Eryx
SRM 412 · 2008-07-30 · by Eryx · Dynamic Programming, Math
Problem Statement
Problem Statement
A string of letters A, B, C is forbidden if there are three consecutive letters from which one is A, one is B, and one is C. For example, BAACAACCBAAA is forbidden, while AABBCCAABB is not.
Your task is to calculate how many such strings of length n are not forbidden.
Your task is to calculate how many such strings of length n are not forbidden.
Constraints
- n will be between 1 and 30, inclusive.
Examples
0)
2 Returns: 9
All 9 strings of length 2 are not forbidden.
1)
3 Returns: 21
There are 27 strings of length 3. Of these, 6 contain one occurrence of each letter. Those 6 strings are forbidden, so you should return 21.
2)
4 Returns: 51
3)
1 Returns: 3
4)
5 Returns: 123
Submissions are judged against all 30 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ForbiddenStrings with a public method long long countNotForbidden(int n) · 30 test cases · 2 s / 256 MB per case