E. Lock Puzzle

Codeforces

IDCF937E

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsstrings

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]

欢迎来到另一个破解密码锁的任务！探险家 Whitfield 和 Martin 发现了一个不寻常的保险箱，据传言，里面藏有无尽的财宝，其中甚至包括离散对数问题的解！当然，保险箱上安装了一个密码锁。锁的屏幕会显示一个由 #cf_span[n] 个小写拉丁字母组成的字符串。初始时，屏幕显示字符串 #cf_span[s]。Whitfield 和 Martin 发现，当屏幕显示字符串 #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[s] 和 #cf_span[t]，每个均由 #cf_span[n] 个小写拉丁字母组成。如果无法在不超过 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[s] 和 #cf_span[t]，每个均由 #cf_span[n] 个小写拉丁字母组成。 ## 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]

**Definitions** Let $\Sigma$ be the set of lowercase Latin letters. Let $\mathcal{S}_n$ be the set of strings over $\Sigma$ of length $n$. For a string $w \in \mathcal{S}_k$, let $w^R$ denote the reversal of $w$. Let concatenation of strings be denoted by juxtaposition. Define the transformation function $f: \mathcal{S}_n \times \{0, \dots, n\} \to \mathcal{S}_n$. For a string $p \in \mathcal{S}_n$ and an integer $x$, let $p = \alpha\beta$ where: * $\alpha$ is the prefix of $p$ of length $n-x$. * $\beta$ is the suffix of $p$ of length $x$. The operation is defined as: $$f(p, x) = \beta^R \alpha$$ **Given** * An integer $n$ such that $1 \le n \le 2000$. * An initial string $s \in \mathcal{S}_n$. * A target string $t \in \mathcal{S}_n$. **Objective** Determine if there exists a sequence of integers $X = (x_1, x_2, \dots, x_k)$ satisfying the following conditions: 1. $0 \le k \le 6100$. 2. $0 \le x_i \le n$ for all $1 \le i \le k$. 3. Let the sequence of strings $(s_0, s_1, \dots, s_k)$ be defined recursively: * $s_0 = s$ * $s_i = f(s_{i-1}, x_i)$ for $1 \le i \le k$ 4. $s_k = t$. **Output** * If such a sequence $X$ exists, output $k$ followed by the terms $x_1, x_2, \dots, x_k$. * Otherwise, output $-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": "E. 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": "CF937E"
  },
  "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": "欢迎来到另一个破解密码锁的任务！探险家 Whitfield 和 Martin 发现了一个不寻常的保险箱，据传言，里面藏有无尽的财宝，其中甚至包括离散对数问题的解！\n\n当然，保险箱上安装了一个密码锁。锁的屏幕会显示一个由 #cf_span[n] 个小写拉丁字母组成的字符串。初始时，屏幕显示字符串 #cf_span[s]。Whitfield 和 Martin 发现，当屏幕显示字符串 #cf_span[...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**\n\nLet $\\Sigma$ be the set of lowercase Latin letters.\nLet $\\mathcal{S}_n$ be the set of strings over $\\Sigma$ of length $n$.\nFor a string $w \\in \\mathcal{S}_k$, let $w^R$ denote the rev...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments