30528번 - Prof. Fumblemore and the Collatz Conjecture 다국어

The Collatz function, C(n), on positive integers is:

n/2 if n is even and 3n+1 if n is odd

The Collatz sequence, CS(n), of a positive integer, n, is the sequence

CS(n) = n, C(n), C(C(n)), C(C(C(n))), ...

For example, CS(12) = 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

The Collatz Conjecture (also known as the 3n+1 problem) is that CS(n) for every positive integer n eventually ends repeating the sequence 4, 2, 1. To date, the status of this conjecture is still unknown. No proof has been given and no counterexample has been found up to very large values.

Prof. Fumblemore wants to study the problem using Collatz sequence types. The Collatz sequence type (CST) of an integer n, CST(n) is a sequence of letters E and O (for even and odd) which describe the parity of the values in CS(n) up to but not including the first power of 2. So,

CST(12) = EEOEO

Note that

CS(908) = 908, 454, 227, 682, 341, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 3, 2, ...

so 12 and 908 have the same CST.

Prof. Fumblemore needs a program which allows him to enter a sequence of E's and O's and returns the smallest integer n for which the given sequence is CST(n).

Notes:

• E's are even numbers which are not powers of 2,
• O's are odd numbers greater than 1.
• The last letter in a sequence must be an O (if C(n) is a power of 2, so is n)
• There can not be two O's in succession (C(odd) = even)
• Since, Prof. Fumblemore does not type well, you must check that the input sequence is valid before attempting to find n. That is, the sequence contains only E's and O's, ends in O and no two O's are adjacent.

Input consists of one line containing a string of up to 50 letters composed of E's and O's.

There is one line of output that consists of the string INVALID if the input line is invalid, or a single decimal integer, n, such that n is the smallest integer for which CST(n) is the input sequence. Input will be chosen such that n ≤ 2⁴⁷.