I :: RATS
Time Limit: 1 Second Memory Limit: 65536 KB
A RATS sequence in base 10 is started by a positive decimal integer. From a number i in the sequence, the next term is generated by adding i to its reverse and sorting the digits. For instance, the next term after 12334444 is 55667777. Also the next term after 44556 is 111 (after dropping the leading zeros):
2334444 + 44443321 = 56777765 -> 55667777
44556 + 65544 = 110100 -> 111
According to a conjecture, each RATS sequence enters either a repeat, or a chain.
The sequence starting with 123 for example enters a repeat when 444 appears for the second time:
123, 444, 888, 1677, 3489, 12333, 44556, 111, 222, 444, 888, ...
A sequence enters a chain when a term of the form 1233*4444 or 5566*7777 appears (3* means one or more consecutive digits 3). In this case, the number of 3’s and 6’s increase steadily and the terms go to infinity. Below is an example:
12334444, 55667777, 123334444, 556667777, 1233334444, 5566667777, ...
Your program should identify whether a RATS sequence enters a repeat or a chain during the first M terms.
Input
The first line of the input includes the number of test cases, 1≤t≤10000. Each test case consists of a line containing two integers: the number of RATS sequence terms to compute (1≤M≤60) and the first number in the RATS sequence which is decimal integer with digits in increasing order and having at most 40 digits. The following terms of the RATS sequence might have more than 40 digits.
Output
For each test case, print one line as follows. If the RATS sequence enters a repeat within the first M term, the line follows by an uppercase letter “R” and the index of the term from which the sequence enters a repeat.
For the case of chain, the test case number is followed by the uppercase letter “C” and the index of the term from which the sequence enters a chain.
If the sequence does not enter a repeat or chain, just print the Mth term of the sequence.
Sample Input
3 30 123 30 1 39 12222444456679999
Sample Output
R 10 C 20 122233338889Submit
Source: 13th Iran Nationwide Internet Contest - Final