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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> using namespace std; string shuffle (string &s1, string &s2) { string s; for (int i = 0; i < s1.length(); i++) { s += s2[i]; s += s1[i]; } s1 = s.substr(0, s1.length()); s2 = s.substr(s2.length(), s2.length()); return s; } int main() { string s1, s2, s; int n; while (cin >> n && n) { cin >> s1 >> s2 >> s; string s12 = s1; s12 += s2; string fixS = s12; bool flag = true; int nofs = 0; // number of steps do { nofs++; s12 = shuffle(s1, s2); if (s == s12) flag = false; } while (s12 != fixS && flag && nofs <= 50); cout << (flag ? -1 : nofs) << endl; } return 0; } |
Program code V2.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <cstring> using namespace std; int main() { int n; while( cin >> n && n){ int count = 0; char *first = new char[n+1]; char *second = new char[n+1]; char *third = new char[2 * n+1]; char *result = new char[2 * n+1]; cin >> first; cin >> second; cin >> third; while(strcmp(result, third) && (count < 51)){ for(int i = 0; i < n; i++){ result[2 * i] = second[i]; result[2 * i + 1] = first[i]; } strncpy(first, &result[0], n); strncpy(second, &result[n], n); count++; } cout << ((count < 51) ? count : -1) << endl; } return 0; } |
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.