InverseCollatz
TCO06 Sponsor 2 · 2006-03-01 · by AdminBrett
TCO06 Sponsor 2 · 2006-03-01 · by AdminBrett · Math, Simulation
Problem Statement
Problem Statement
Given a positive integer j greater than 1, the corresponding Collatz
sequence is produced by repeatedly applying f to j (and continues even after we reach 1). The function f behaves as follows:
String s they have written down,
you must return a String of the form (quotes for clarity) "ak+b". Here a
and b are integers with no extra leading zeros. The returned string
must make the following set the collection of all possible numbers
that could have begun the sequence:
{ x/2 if x is even
f(x) = {
{ 3x+1 if x is odd
Suppose someone began with the value y and has started (but not
necessarily finished) generating the Collatz sequence. Each time they
apply f they write down 'E' or 'O' to denote whether the argument was even or odd,
respectively. Given the P = { ak + b | k >= 0 and ak + b > 1}
If there are multiple possible return values, choose the one with b minimal.Constraints
- s will contain between 1 and 50 characters, inclusive.
- Each character in s will be 'E' or 'O'.
- An 'O' will never be immediately followed by another 'O' in s.
Examples
0)
"EOEEEOEOEEEOEOEEOEEOEO" Returns: "32768k+30138"
1)
"OEEEEOEOEEEOEOEEOEOE" Returns: "8192k+4197"
2)
"EOEEEEEEEEOEOEOEOEEEOEE" Returns: "131072k+13482"
3)
"EOEOEEOEOEOEEOEEOEEOEEEOEOEEEEOEOEOEEOE" Returns: "33554432k+31532726"
4)
"OEOEEEEOEEOEOEEEOEEE" Returns: "16384k+6915"
30)
"EEE" Returns: "8k+0"
The argument was even 3 times in a row, so the original value was a positive multiple of 8.
31)
"OE" Returns: "2k+1"
The initial number had to be odd. After multiplying by 3 and adding 1, the next value will definitely be even.
Submissions are judged against all 43 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class InverseCollatz with a public method string getForm(string s) · 43 test cases · 2 s / 256 MB per case