The First Term
InterviewTime limit1sMemory limit128 MB
Trace each given term backward through the reverse look-and-say rule until it reaches its earliest valid ancestor.
- Level
Medium5 of 10
- Topics
- Simulation, String
- Solved
- No attempts yet
Problem
The sequence below continues by a fixed rule.
1, 11, 21, 1211, 111221, ...
To build the next term, split the current term into blocks of equal consecutive digits. For each block write how many times the digit repeats, then the digit itself, and concatenate the blocks in order. For example 21 is one 2 and one 1, so the next term is 1211. By the same rule 111221 is three 1s, two 2s and one 1, so the term after it is 312211.
Running the rule backwards gives the previous term. 2221 means two 2s and two 1s, so its previous term is 2211, and the previous term of 2211 is 221. 221 has no previous term, because an odd number of digits cannot be split into (count, digit) pairs. 2212 has no previous term either. Read as pairs it says two 2s and one 2, which is 222, but the term after 222 is 32, not 2212.
Given a term n, find the first term of the sequence in which n appears. The first term is the term that has no previous term. For n = 2221 the answer is 221, and for n = 312211 the answer is 1. When the previous term equals the term itself, as with 22, that term counts as the first term.
Input
The input holds several test cases. Each line contains one integer n of at most 100 digits. The last line contains 0 and is not processed.
Output
For each test case print one line in the form Test i: a, where i is the test case number starting at 1 and a is the first term.