1015B.md (2221B)
1 Source: https://codeforces.com/problemset/problem/1015/B 2 3 B. Obtaining the String 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two strings $s$ and $t$. Both strings have length $n$ and consist of lowercase Latin letters. The characters in the strings are numbered from $1$ to $n$. 22 23 You can successively perform the following move any number of times (possibly, zero): 24 25 * swap any two adjacent (neighboring) characters of $s$ (i.e. for any $i = \{1, 2, \dots, n - 1\}$ you can swap $s_i$ and $s_{i + 1})$. 26 27 You can't apply a move to the string $t$. The moves are applied to the string $s$ one after another. 28 29 Your task is to obtain the string $t$ from the string $s$. Find any way to do it with at most $10^4$ such moves. 30 31 You do not have to minimize the number of moves, just find any sequence of moves of length $10^4$ or less to transform $s$ into $t$. 32 33 Input 34 35 The first line of the input contains one integer $n$ ($1 \le n \le 50$) — the length of strings $s$ and $t$. 36 37 The second line of the input contains the string $s$ consisting of $n$ lowercase Latin letters. 38 39 The third line of the input contains the string $t$ consisting of $n$ lowercase Latin letters. 40 41 Output 42 43 If it is impossible to obtain the string $t$ using moves, print "-1". 44 45 Otherwise in the first line print one integer $k$ — the number of moves to transform $s$ to $t$. Note that $k$ must be an integer number between $0$ and $10^4$ inclusive. 46 47 In the second line print $k$ integers $c_j$ ($1 \le c_j \lt n$), where $c_j$ means that on the $j$-th move you swap characters $s_{c_j}$ and $s_{c_j + 1}$. 48 49 If you do not need to apply any moves, print a single integer $0$ in the first line and either leave the second line empty or do not print it at all. 50 51 Examples 52 53 Input 54 55 ``` 56 6 57 abcdef 58 abdfec 59 ``` 60 61 Output 62 63 ``` 64 4 65 3 5 4 5 66 ``` 67 68 Input 69 70 ``` 71 4 72 abcd 73 accd 74 ``` 75 76 Output 77 78 ``` 79 -1 80 ``` 81 82 Note 83 84 In the first example the string $s$ changes as follows: "abcdef" $\rightarrow$ "abdcef" $\rightarrow$ "abdcfe" $\rightarrow$ "abdfce" $\rightarrow$ "abdfec". 85 86 In the second example there is no way to transform the string $s$ into the string $t$ through any allowed moves.