/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋君は双六で遊んでいます。
この双六には 0 から N までの番号がついた N + 1 個のマスがあります。高橋君はマス 0 からスタートし、ゴールするにはマス N にちょうど止まらなければなりません。
この双六では、1 から M までの M 種類の目が出るルーレットを使います。各手番で、高橋君はルーレットを回して出た目の数だけ進みます。この結果マス N を越えて進むことになる場合、ゲームオーバーとなります。
また、いくつかのマスは「ゲームオーバーマス」であり、それらのマスに止まってもゲームオーバーとなります。マスの情報は長さ N + 1 の文字列 S で与えられます。各 i (0 \leq i \leq N) について、S[i] = 1 のときマス i はゲームオーバーマスであり、S[i] = 0 のときマス i はゲームオーバーマスではありません。
高橋君がゲームオーバーとならずに最短手数でゴールするときの出目を順に答えてください。そのような目の出方が複数存在するときは、そのうち出目の列が辞書順で最小であるものを出力してください。ゲームオーバーとならずにゴールすることが不可能である場合は、 -1 を出力してください。
制約
- 1 ≤ N ≤ 10^5
- 1 ≤ M ≤ 10^5
- |S| = N + 1
- S は
0と1から成る - S[0] =
0 - S[N] =
0
入力
入力は以下の形式で標準入力から与えられる。
N M S
出力
ゴールすることが可能である場合、そのような最短の出目の列のうち辞書順で最小のものを出力せよ。ゴールすることが不可能である場合、-1 を出力せよ。
入力例 1
9 3 0001000100
出力例 1
1 3 2 3
1 , 3 , 2 , 3 の順に目を出すと、高橋君はマス 1 , 4 , 6 を経由してマス 9 に到達することが出来ます。高橋君が 3 手以内にマス 9 に到達することは不可能であり、また 4 手でマス 9 に到達するような出目の列の中ではこれが辞書順で最小です。
入力例 2
5 4 011110
出力例 2
-1
高橋君はマス 5 に到達することが出来ません。
入力例 3
6 6 0101010
出力例 3
6
Score : 600 points
Problem Statement
Takahashi is playing a board game called Sugoroku.
On the board, there are N + 1 squares numbered 0 to N. Takahashi starts at Square 0, and he has to stop exactly at Square N to win the game.
The game uses a roulette with the M numbers from 1 to M. In each turn, Takahashi spins the roulette. If the number x comes up when he is at Square s, he moves to Square s+x. If this makes him go beyond Square N, he loses the game.
Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string S of length N + 1, representing which squares are Game Over Squares. For each i (0 \leq i \leq N), Square i is a Game Over Square if S[i] = 1 and not if S[i] = 0.
Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print -1.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- |S| = N + 1
- S consists of
0and1. - S[0] =
0 - S[N] =
0
Input
Input is given from Standard Input in the following format:
N M S
Output
If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.
If Takahashi cannot win the game, print -1.
Sample Input 1
9 3 0001000100
Sample Output 1
1 3 2 3
If the numbers 1, 3, 2, 3 come up in this order, Takahashi can reach Square 9 via Square 1, 4, and 6. He cannot reach Square 9 in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square 9 in four turns.
Sample Input 2
5 4 011110
Sample Output 2
-1
Takahashi cannot reach Square 5.
Sample Input 3
6 6 0101010
Sample Output 3
6