C. Lock Puzzle

Codeforces

IDCF936C

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsimplementationstrings

English · Original

Chinese · Translation

Formal · Original

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. ## Input The first line contains an integer _n_, the length of the strings _s_ and _t_ (1 ≤ _n_ ≤ 2 000). After that, there are two strings _s_ and _t_, consisting of _n_ lowercase Latin letters each. ## Output 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. [samples]

欢迎来到另一个破解密码锁的任务！探险家惠特菲尔德和马丁发现了一个不寻常的保险箱，据传言，里面藏有无尽的财富，其中甚至包括离散对数问题的解！当然，保险箱上安装了一个密码锁。锁的屏幕上会显示一个由 #cf_span[n] 个小写拉丁字母组成的字符串。初始时，屏幕显示字符串 #cf_span[s]。惠特菲尔德和马丁发现，当屏幕上显示字符串 #cf_span[t] 时，保险箱就会打开。可以通过操作 «_shift_ #cf_span[x]» 来改变屏幕上的字符串。为了执行此操作，探险家们选择一个整数 #cf_span[x]，范围从 0 到 #cf_span[n]（包含两端）。随后，当前字符串 #cf_span[p = αβ] 会变为 #cf_span[βRα]，其中 #cf_span[β] 的长度为 #cf_span[x]，#cf_span[α] 的长度为 #cf_span[n - x]。换句话说，字符串 #cf_span[p] 的长度为 #cf_span[x] 的后缀会被反转并移动到字符串的开头。例如，执行操作 «_shift_ #cf_span[4]» 后，字符串 «_abcacb_» 会变为 «_bcacab_»，因为 #cf_span[α = ]_ab_，#cf_span[β = ]_cacb_，#cf_span[βR = ]_bcac_。探险家们担心，如果应用过多的 «_shift_» 操作，锁可能会永久锁定。他们请你找出一种方法，在不超过 #cf_span[6100] 次操作的情况下，将屏幕上的字符串变为 #cf_span[t]。第一行包含一个整数 #cf_span[n]，表示字符串 #cf_span[s] 和 #cf_span[t] 的长度（#cf_span[1 ≤ n ≤ 2 000]）。接下来是两个长度均为 #cf_span[n] 的小写拉丁字母字符串 #cf_span[s] 和 #cf_span[t]。如果无法在不超过 6100 次 «_shift_» 操作的情况下从字符串 #cf_span[s] 得到字符串 #cf_span[t]，请输出一个单独的数字 #cf_span[ - 1]。否则，在第一行输出操作次数 #cf_span[k]（#cf_span[0 ≤ k ≤ 6100]）。在下一行输出 #cf_span[k] 个数字 #cf_span[xi]，对应按顺序应用的 «_shift_ #cf_span[xi]» 操作（#cf_span[0 ≤ xi ≤ n]）。在第一个示例中，应用操作后，屏幕上的字符串将按如下方式变化： ## Input 第一行包含一个整数 #cf_span[n]，表示字符串 #cf_span[s] 和 #cf_span[t] 的长度（#cf_span[1 ≤ n ≤ 2 000]）。接下来是两个长度均为 #cf_span[n] 的小写拉丁字母字符串 #cf_span[s] 和 #cf_span[t]。 ## Output 如果无法在不超过 6100 次 «_shift_» 操作的情况下从字符串 #cf_span[s] 得到字符串 #cf_span[t]，请输出一个单独的数字 #cf_span[ - 1]。否则，在第一行输出操作次数 #cf_span[k]（#cf_span[0 ≤ k ≤ 6100]）。在下一行输出 #cf_span[k] 个数字 #cf_span[xi]，对应按顺序应用的 «_shift_ #cf_span[xi]» 操作（#cf_span[0 ≤ xi ≤ n]）。 [samples]

Let $ n \in \mathbb{N} $, $ s, t \in \Sigma^n $ where $ \Sigma $ is the set of lowercase Latin letters. Define an operation $ \text{shift}(x) $ for $ x \in \{0, 1, \dots, n\} $: Given a string $ p = \alpha \beta $ with $ |\alpha| = n - x $, $ |\beta| = x $, then $ \text{shift}(x)(p) = \beta^R \alpha $, where $ \beta^R $ denotes the reverse of $ \beta $. **Given:** - Initial string: $ s $ - Target string: $ t $ **Objective:** Find a sequence of operations $ x_1, x_2, \dots, x_k $ with $ 0 \leq k \leq 6100 $, such that $$ \text{shift}(x_k) \circ \cdots \circ \text{shift}(x_1)(s) = t $$ If no such sequence exists, output $ -1 $. **Constraints:** - $ 1 \leq n \leq 2000 $ - Each $ x_i \in \{0, 1, \dots, n\} $ - $ k \leq 6100 $ **Output:** - If solvable: $ k $, followed by $ x_1, x_2, \dots, x_k $ - Otherwise: $ -1 $

Samples

Input #1

6
abacbb
babcba

Output #1

4
6 3 2 3

Input #2

3
aba
bba

Output #2

\-1

In the first example, after applying the operations, the string on the screen will change as follows:

1.  _abacbb_ _bbcaba_
2.  _bbcaba_ _ababbc_
3.  _ababbc_ _cbabab_
4.  _cbabab_ _babcba_

API Response (JSON)

{
  "problem": {
    "name": "C. Lock Puzzle",
    "description": {
      "content": "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 fin",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF936C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 fin...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "欢迎来到另一个破解密码锁的任务！探险家惠特菲尔德和马丁发现了一个不寻常的保险箱，据传言，里面藏有无尽的财富，其中甚至包括离散对数问题的解！\n\n当然，保险箱上安装了一个密码锁。锁的屏幕上会显示一个由 #cf_span[n] 个小写拉丁字母组成的字符串。初始时，屏幕显示字符串 #cf_span[s]。惠特菲尔德和马丁发现，当屏幕上显示字符串 #cf_span[t] 时，保险箱就会打开。\n\n可以通过操作...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n \\in \\mathbb{N} $, $ s, t \\in \\Sigma^n $ where $ \\Sigma $ is the set of lowercase Latin letters.\n\nDefine an operation $ \\text{shift}(x) $ for $ x \\in \\{0, 1, \\dots, n\\} $:  \nGiven a string $ p ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments