Analysis: Secret Code by Brian Dean
This problem has a recursive solution where we check, for a string S, whether it could have been created according to each of our 4 rules from a shorter string S' (where we use recursion to then count the number of ways to get S'). Code is shown below (we subtract one at the end since otherwise we would count the base case solution where S is produced with zero applications of our rule, and we require one or more applications).
Since the input can be quite large (length at most 100), we should
consider whether this approach will run quickly enough. If we
start with a string of length N, then at worst, we will generate:
4 recursive calls on strings of length roughly N/2,
16 recursive calls on strings of length roughly N/4,
64 recursive calls on strings of length roughly N/8,
and so on. By the time we get to recursive calls on strings of length
N/64 we will reach our base case, so by the pattern above we will see
at most 46 = 212 = 4096 such calls, which is
a very small number. We therefore expect this approach to run
quite fast for strings of length 100 (if the input size was
much larger, however, we would be in trouble).
#include <string> #include <iostream> #include <fstream> using namespace std; int numways(string s) { int ans = 1, L = s.length(); if (L % 2 == 0 || L == 1) return 1; // ABC -> AB + ABC if (s.substr(0,L/2) == s.substr(L/2,L/2)) ans += numways(s.substr(L/2,L/2+1)); // ABC -> ABC + AB if (s.substr(0,L/2) == s.substr(L/2+1,L/2)) ans += numways(s.substr(0,L/2+1)); // ABC -> BC + ABC if (s.substr(0,L/2) == s.substr(L/2+1,L/2)) ans += numways(s.substr(L/2,L/2+1)); // ABC -> ABC + BC if (s.substr(1,L/2) == s.substr(L/2+1,L/2)) ans += numways(s.substr(0,L/2+1)); return ans; } int main() { ifstream fin("scode.in"); ofstream fout("scode.out"); string s; fin >> s; fout << numways(s) - 1 << endl; return 0; }