e-olymp 6901. Shuffling Strings

Task

Suppose $S_1$ and $S_2$  are two strings of size $n$ consisting of characters $A$ through $H$ (capital letters). We plan to perform the following step several times to produce a given string $S$. In each step we shuffle $S_1$ and $S_2$ to get string $S_{12}$ Indeed, $S_{12}$ is obtained by scanning $S_1$ and $S_2$ from left to right and putting their characters alternatively in $S_{12}$ from left to right.

The shuffling operation always starts with the leftmost character of $S_2$. After this operation, we set $S_1$ and $S_2$ to be the first half and the second half of $S_{12}$, respectively. For instance, if $S_1 = ABCHAD$ and $S_2 = DEFDAC$, then $S_12 = DAEBFCDHAACD$, and for the next step $S_1 = DAEBFC$ and $S_2 = DHAACD$. For the given string $S$ of size $2n$, the goal is to determine whether $S_{12} = S$ at some step.

Input

There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers [latex] 0 \le n \le 100 [/latex] which is the length of $S_1$ and $S_2$. The remainder of each test case consists of three lines. The first and the second lines contain strings $S_1$ and $S_2$ with size $n$, respectively, and the last line contains string $S$ with size $2n$. The input terminates with «$0$» which should not be processed.

Output

For each test case, output $-1$ if $S$ is not reachable. Otherwise, output the minimum number of steps to reach $S$ . To make your life easier, we inform you that the output is not greater than $50$ for the given input.

Tests

Input Output
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC
0
2
-1
3
DBC
BCD
CDBCBD
0
-1
3
DABC
ABCD
CADBCBAD
1
A
B
AB
0
-1
2
3
AAA
AAA
AAAAAA
0
1
5
ABACD
ACABB
AAAACCBBBD
0
-1

Program code

Program code V2.

Solution

Repeating the shuffling of the two strings a sufficient number of times, it becomes clear that the variations of the lines repeat with a certain periodicity. In order not to continue the cycle of shuffling if strings began to repeat, we fix the first concatenation of the strings $S_1$ and $S_2$, and if we meet it again, we assume that the string $S$ cannot be obtained. Also a sign of this is that the number of steps exceeded $50$ — from the condition of the problem.

Links

Related Images: