[CCO 2023] Flip it and Stick it

Luogu

IDLGP10069

Time1000ms

Memory1024MB

DifficultyP5

贪心2023CCO（加拿大）构造分类讨论

Finn 正在玩一款叫做「Flip it and Stick it」的游戏，简称为 FiSi。FiSi 是一款单人游戏，玩法是在两个由 0 和 1 组成的字符串 $S$ 和 $T$ 上进行操作。Finn 可以进行以下形式的操作：选择 $S$ 的一个子串并将其翻转，然后将字符串的各部分按照原来的顺序粘贴在一起，形成新的字符串 $S$。例如，Finn 可以取字符串 $S=101100$，取从第 2 位开始的子串 $011$（字符串的编号是从 $1$ 开始的），并在一次操作中创建字符串 $S=111000$。如果 $S$ 不包含 $T$ 作为子串，Finn 就赢得了游戏。你的任务是帮助 Finn 确定赢得游戏所需的最短操作序列的长度，或者告诉他游戏无法获胜。 ## Input 第一行一个字符串 $S$。第二行一个字符串 $T$。 ## Output 输出一行一个整数，表示如果能赢得游戏所需的最少操作次数，否则输出 $-1$。 [samples] ## Note **样例解释 1** Finn 从字符串 $100110$ 开始。他无法通过一次操作后使得 $10$ 不为子串，但他可以在两次操作后做到。例如，他的第一次操作可以是翻转从第 4 位到第 6 位的子串（$110$），得到 $100011$。然后，他的第二次操作可以是翻转从第 1 位到第 4 位的子串（$1000$），得到 $000111$，它不包含 $10$ 作为子串。 **样例解释 2** 无论 Finn 进行多少次操作，字符串 $T$ 总会是 $S$ 的子串。对于所有的数据，有 $1 \leq|S| \leq 2\times 10^5$，$1 \leq|T| \leq 3$。设 $|T|=l$。 | 子任务编号 | 分值 | $l$ 的限制 | | :-:|:-:|:-:| |1| 4| $l=1$| |2| 12| $l=2, T_{1} \neq T_{2}$| |3| 16| $l=2$| |4| 20| $l=3, T_{1} \neq T_{3}$| |5| 20| $l=3,T_{1} \neq T_{2}$| |6| 28| $l=3$|

Samples

Input #1

100110
10

Output #1

Input #2

000
00

Output #2

-1

API Response (JSON)

{
  "problem": {
    "name": "[CCO 2023] Flip it and Stick it",
    "description": {
      "content": "Finn 正在玩一款叫做「Flip it and Stick it」的游戏，简称为 FiSi。FiSi 是一款单人游戏，玩法是在两个由 0 和 1 组成的字符串 $S$ 和 $T$ 上进行操作。Finn 可以进行以下形式的操作： 选择 $S$ 的一个子串并将其翻转，然后将字符串的各部分按照原来的顺序粘贴在一起，形成新的字符串 $S$。 例如，Finn 可以取字符串 $S=101100$，取从第 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10069"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Finn 正在玩一款叫做「Flip it and Stick it」的游戏，简称为 FiSi。FiSi 是一款单人游戏，玩法是在两个由 0 和 1 组成的字符串 $S$ 和 $T$ 上进行操作。Finn 可以进行以下形式的操作：\n\n选择 $S$ 的一个子串并将其翻转，然后将字符串的各部分按照原来的顺序粘贴在一起，形成新的字符串 $S$。\n例如，Finn 可以取字符串 $S=101100$，取从第 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments