304930: CF936C. Lock Puzzle

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Lock Puzzle

题意翻译

### 题目描述 探险家发现了一个保险箱,里面有大量的宝藏。 保险箱上有一个密码锁,初始时显示的是一个长度为$n$的小写字母字符串$s$。探险家发现,当密码锁上显示的是字符串$t$时,这个密码锁就会打开。 密码锁显示的字符串可以通过形如`shift x`的指令改变。要执行这个指令,探险家需要在$0$到$n$的范围内(包含$0$和$n$)选择一个$x$。此时,设屏幕上显示的字符串$p = \alpha\beta$(其中$\beta$的长度为$x$),那么这个字符串会变为$\beta^{R}\alpha$($\beta^{R}$表示$\beta$反转后的结果)。 比如,如果屏幕上当前显示$abcacb$,那么执行`shift 4`后屏幕上会显示$bcacab$,因为$\alpha=ab$,$\beta=cacb$,$\beta^{R}=baca$。 探险家担心如果执行了太多了`shift`操作,这个密码锁就会永远锁定。因此,他会给你$n$和字符串$s$和$t$,并且请你给出一个步骤数不大于$6100$的解锁方案。请注意无需最小化步骤数。 ### 输入格式 第一行一个整数$n$,为字符串$s$和$t$的长度。 随后两行分别输入小写字母构成的字符串$s$和$t$,表示初始时屏幕显示的字符串以及解锁前需要得到的字符串。 ### 输出格式 如果不可能打开密码锁,输出`-1`。 否则,第一行输出一个整数$k\ (0\leq k \leq 6100)$,表示需要的操作数量。第二行输出$k$个空格隔开的整数$x_i\ (0\leq x_i \leq n)$,其中$x_i$代表执行操作$shift\ x_i$。 ### 数据范围 $1 \leq n \leq 2000$

题目描述

Welcome to another task about breaking the code lock! Explorers Whitfield and Martin came across an unusual safe, inside of which, according to rumors, there are untold riches, among which one can find the solution of the problem of discrete logarithm! Of course, there is a code lock is installed on the safe. The lock has a screen that displays a string of $ n $ lowercase Latin letters. Initially, the screen displays string $ s $ . Whitfield and Martin found out that the safe will open when string $ t $ will be displayed on the screen. The string on the screen can be changed using the operation «shift $ x $ ». In order to apply this operation, explorers choose an integer $ x $ from 0 to $ n $ inclusive. After that, the current string $ p=αβ $ changes to $ β^{R}α $ , where the length of $ β $ is $ x $ , and the length of $ α $ is $ n-x $ . In other words, the suffix of the length $ x $ of string $ p $ is reversed and moved to the beginning of the string. For example, after the operation «shift $ 4 $ » the string «abcacb» will be changed with string «bcacab », since $ α= $ ab, $ β= $ cacb, $ β^{R}= $ bcac. Explorers are afraid that if they apply too many operations «shift», the lock will be locked forever. They ask you to find a way to get the string $ t $ on the screen, using no more than $ 6100 $ operations.

输入输出格式

输入格式


The first line contains an integer $ n $ , the length of the strings $ s $ and $ t $ ( $ 1<=n<=2000 $ ). After that, there are two strings $ s $ and $ t $ , consisting of $ n $ lowercase Latin letters each.

输出格式


If it is impossible to get string $ t $ from string $ s $ using no more than 6100 operations «shift», print a single number $ -1 $ . Otherwise, in the first line output the number of operations $ k $ ( $ 0<=k<=6100 $ ). In the next line output $ k $ numbers $ x_{i} $ corresponding to the operations «shift $ x_{i} $ » ( $ 0<=x_{i}<=n $ ) in the order in which they should be applied.

输入输出样例

输入样例 #1

6
abacbb
babcba

输出样例 #1

4
6 3 2 3

输入样例 #2

3
aba
bba

输出样例 #2

-1

Input

题意翻译

### 题目描述 探险家发现了一个保险箱,里面有大量的宝藏。 保险箱上有一个密码锁,初始时显示的是一个长度为$n$的小写字母字符串$s$。探险家发现,当密码锁上显示的是字符串$t$时,这个密码锁就会打开。 密码锁显示的字符串可以通过形如`shift x`的指令改变。要执行这个指令,探险家需要在$0$到$n$的范围内(包含$0$和$n$)选择一个$x$。此时,设屏幕上显示的字符串$p = \alpha\beta$(其中$\beta$的长度为$x$),那么这个字符串会变为$\beta^{R}\alpha$($\beta^{R}$表示$\beta$反转后的结果)。 比如,如果屏幕上当前显示$abcacb$,那么执行`shift 4`后屏幕上会显示$bcacab$,因为$\alpha=ab$,$\beta=cacb$,$\beta^{R}=baca$。 探险家担心如果执行了太多了`shift`操作,这个密码锁就会永远锁定。因此,他会给你$n$和字符串$s$和$t$,并且请你给出一个步骤数不大于$6100$的解锁方案。请注意无需最小化步骤数。 ### 输入格式 第一行一个整数$n$,为字符串$s$和$t$的长度。 随后两行分别输入小写字母构成的字符串$s$和$t$,表示初始时屏幕显示的字符串以及解锁前需要得到的字符串。 ### 输出格式 如果不可能打开密码锁,输出`-1`。 否则,第一行输出一个整数$k\ (0\leq k \leq 6100)$,表示需要的操作数量。第二行输出$k$个空格隔开的整数$x_i\ (0\leq x_i \leq n)$,其中$x_i$代表执行操作$shift\ x_i$。 ### 数据范围 $1 \leq n \leq 2000$

加入题单

上一题 下一题 算法标签: