Problem E
encryptedcounting
You and your friends have devised a clever method of encrypting numbers and have been using the method to talk to each other for the past few days. Unfortunately, your decryption tool broke so you need to create a new one.
The encryption is based on a sequence, where the next element of the sequence is derived by the “spoken” representation of the previous element. The encrypted version of a number, $M$, is derived by finding the $M^{th}$ member of the sequence starting from some initial seed, $S$. To decrypt a ciphertext, $C$, one needs to find how many $M$ iterations it took to reach that $C$ from the given seed, $S$.
Here is an example of how the sequence is generated:
// Comments describe how the number on the left // was generated from the previous number. 0. 12 // "12" is our seed 1. 1112 // "12" is "one one" and "one two" -> 11, 12 -> 1112 2. 3112 // "1112" is "three ones" and "one two" -> 31, 12 -> 3112 3. 132112 // "3112" is "one three" and "two ones" and "one two" -> 132112 4. 1113122112 5. 311311222112
Your friend sends you a single line containing the seed, $S$, and the ciphertext, $C$. Output the decrypted number, $M$, which describes the number of iterations your encryption algorithm takes to reach $C$ when starting at $S$.
Input
Two integers, $S$ and $C$, that are separated by a space. $S$ has less than $10$ digits, and $C$ has less than $200$ digits. Suppose the input is:
12 132112
where $S = 12$ and $C = 132112$. You then need to calculate, $M$, which would be $3$ in this case (since the third iteration of the seed produces $132112$).
Output
Output a single integer, $M$, that is the number of iterations it takes to reach $C$ from the seed $S$. The output for the above example would look like:
3
| Sample Input 1 | Sample Output 1 |
|---|---|
12 132112 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
21 13211311123113112211 |
7 |
