codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.