Sugoroku

题目描述

Takahashi 正在玩一种叫做 Sugoroku 的棋盘游戏。 棋盘上有 $N + 1$ 个格子，编号为 $0$ 到 $N$。Takahashi 从格子 $0$ 出发，他必须恰好停在格子 $N$ 才能赢得游戏。 游戏使用一个刻有 $1$ 到 $M$ 这些数字的轮盘。在每一回合，Takahashi 旋转轮盘。如果当他位于格子 $s$ 时转到数字 $x$，他就移动到格子 $s+x$。如果这使他越过了格子 $N$，他就输掉游戏。 此外，某些格子是“游戏结束格”。如果他停在这些格子之一，他也会输掉游戏。你得到一个长度为 $N + 1$ 的字符串 $S$，表示哪些格子是游戏结束格。对于每个 $i$ $(0 \leq i \leq N)$，当 $S[i] = 1$ 时格子 $i$ 是游戏结束格，若 $S[i] = 0$ 则不是。 找到一串轮盘出现的数字，使得 Takahashi 能以尽可能少的回合数赢得游戏。如果存在多条这样的序列，找出字典序最小的序列。如果 Takahashi 无法赢得游戏，输出 $-1$。

输入格式

输入由标准输入给出，格式如下： $N$ $M$ $S$

输出格式

如果 Takahashi 能赢得游戏，打印在最短回合数内使他赢得游戏的所有序列中字典序最小的序列，数字之间用空格分隔。 如果 Takahashi 无法赢得游戏，打印 $-1$。

9 3
0001000100

1 3 2 3

5 4
011110

-1

6 6
0101010

6

提示

$1 \leq N \leq 10^5$ $1 \leq M \leq 10^5$ $|S| = N + 1$ $S$ 仅由 $0$ 和 $1$ 组成。 $S[0] =$ $0$ $S[N] =$ $0$如果轮盘依次出现数字 $1$、$3$、$2$、$3$，Takahashi 可以通过格子 $1$、$4$ 和 $6$ 到达格子 $9$。他不可能在三回合或更少回合内到达格子 $9$，并且这是在四回合内到达格子 $9$ 的字典序最小的序列。
Takahashi 无法到达格子 $5$。

标签: AtCoder|abc146F

来源

AtCoder|abc146F