/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 1000 points
Problem Statement
Snuke participated in a magic show.
A magician prepared N identical-looking boxes. He put a treasure in one of the boxes, closed the boxes, shuffled them, and numbered them 1 through N.
Since the boxes are shuffled, now Snuke has no idea which box contains the treasure. Snuke wins the game if he opens a box containing the treasure. You may think that if Snuke opens all boxes at once, he can always win the game. However, there are some tricks:
- Snuke must open the boxes one by one. After he opens a box and checks the content of the box, he must close the box before opening the next box.
- He is only allowed to open Box i at most a_i times.
- The magician may secretly move the treasure from a closed box to another closed box, using some magic trick. For simplicity, assume that the magician never moves the treasure while Snuke is opening some box. However, he can move it at any other time (before Snuke opens the first box, or between he closes some box and opens the next box).
- The magician can perform the magic trick at most K times.
Can Snuke always win the game, regardless of the initial position of the treasure and the movements of the magician?
Constraints
- 2 \leq N \leq 50
- 1 \leq K \leq 50
- 1 \leq a_i \leq 100
Input
Input is given from Standard Input in the following format:
N K a_1 a_2 \cdots a_N
Output
If the answer is no, print a single -1.
Otherwise, print one possible move of Snuke in the following format:
Q x_1 x_2 \cdots x_Q
It means that he opens boxes x_1, x_2, \cdots, x_Q in this order.
In case there are multiple possible solutions, you can output any.
Sample Input 1
2 1 5 5
Sample Output 1
7 1 1 2 1 2 2 1
If Snuke opens the boxes 7 times in the order 1 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 2 \rightarrow 1, he can always find the treasure regardless of its initial position and the movements of the magician.
Sample Input 2
3 50 5 10 15
Sample Output 2
-1
配点 : 1000 点
問題文
すぬけ君はマジックショーでの勝負に参加しました。
ショーのマジシャンは、見た目が同じ N 個の箱を用意していました。 彼はそのうち一つに財宝を入れてからそれらの箱を閉じ、箱の順番を無作為に入れ替えてから 1 から N までの番号を振りました。
箱の順番を入れ替えられてしまったので、どの箱に財宝が入っているかはすぬけ君には分からなくなりました。 この勝負は、すぬけ君が財宝の入った箱を開けることができれば彼の勝ちです。 それなら、すべての箱を一斉に開ければ必ず勝てるではないかと思われるかもしれません。 しかし、以下のようにいくつか特殊なルールがあります。
- すぬけ君は、箱を一つずつ開けなければならない。一つの箱を開けてその中身を確認したら、その箱は次の箱を開ける前に閉じなければならない。
- 箱 i は、最大で a_i 回しか開けてはならない。
- マジシャンは、何らかの手品を用いて閉じた箱から別の閉じた箱に財宝を移すことがある。 簡略化のため、すぬけ君がいずれかの箱を開けている間に財宝が移されることはないとしてよいが、それ以外のあらゆる機会 (すぬけ君が最初に箱を開ける前、またはすぬけ君がいずれかの箱を閉じてから次の箱を開けるまでの間) に財宝が移される可能性がある。
- マジシャンは、上記の財宝の移動を最大で K 回行う可能性がある。
すぬけ君は、財宝の初期位置やマジシャンがどのように財宝を移動させるかによらず、必ず勝負に勝つことができるでしょうか？
制約
- 2 \leq N \leq 50
- 1 \leq K \leq 50
- 1 \leq a_i \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N K a_1 a_2 \cdots a_N
出力
問題の答えが No であれば、-1 とのみ出力せよ。
そうでなければ、すぬけ君が取りうる戦略をひとつ以下の形式で出力せよ。
Q x_1 x_2 \cdots x_Q
これは、箱 x_1, x_2, \cdots, x_Q をこの順に開けることを表す。
複数の解が考えられる場合は、そのうちのどれを出力してもよい。
入力例 1
2 1 5 5
出力例 1
7 1 1 2 1 2 2 1
1 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 2 \rightarrow 1 の順に 7 回箱を開ければ、財宝の初期位置やマジシャンがどのように財宝を移動させるかによらず、必ず財宝を見つけることができます。
入力例 2
3 50 5 10 15
出力例 2
-1