MultiReplacer
SRM 230 · 2005-02-08 · by AdminBrett
SRM 230 · 2005-02-08 · by AdminBrett · Math
Problem Statement
Problem Statement
Let f be a function that takes a string composed of a's, b's, and c's, and replaces every occurrence of 'a' with arep, 'b' with brep, and 'c' with crep. Your code will compute the length of (quotes for clarity):
f( f( f( ... f(a) ... ) ) ) : f applied iter times to the string "a"Since the lengths can grow very large with only a few iterations, you will return the length mod m. For example, if
arep = abc brep = c crep = ba iter = 3 m = 7then you will find the length of
f(f(f(a))) = f(f(abc)) = f(abccba) = abccbabacabc ,which is 12. Then you will compute 12 mod 7 = 5, and return 5.
Constraints
- arep, brep, and crep will contain between 1 and 50 characters inclusive.
- Each character in arep, brep, and crep will be 'a', 'b', or 'c'.
- iter will be between 1 and 2000000000 inclusive.
- m will be between 2 and 2^31-1 inclusive.
Examples
0)
"abc" "c" "ba" 3 7 Returns: 5
Same as above.
1)
"b" "c" "a" 2000000000 100 Returns: 1
2)
"b" "c" "aa" 30 10000 Returns: 1024
3)
"acabbcabbabac" "cababcababcabcabacbacbabcacb" "acbacbabcababcabababbabcbcab" 2000000000 2000000000 Returns: 1876480521
4)
"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" 1999999997 2000000001 Returns: 1960000001
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MultiReplacer with a public method long long length(string arep, string brep, string crep, int iter, int m) · 57 test cases · 2 s / 256 MB per case