atcoder#AGC002C. [AGC002C] Knot Puzzle
[AGC002C] Knot Puzzle
問題文
本のロープがあります。 ロープは から まで番号が振られています。 ロープ の長さは です。
最初、 について、ロープ の右端とロープ の左端が結ばれています。 高橋君は次の操作を 回行い、すべての結び目をほどこうとしています。
- ひと繋がりのロープのうち、長さの総和が 以上のものをひとつ選ぶ。 選んだひと繋がりのロープに結び目があれば、結び目のうちどれかひとつをほどく。
高橋君は結び目をほどく順番を工夫し、すべての結び目をほどくことができるでしょうか? 可能か判定し、可能ならば結び目をほどく順番をひとつ求めてください。
制約
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
出力
すべての結び目をほどくことができないならば、Impossible
を出力せよ。
すべての結び目をほどくことができるならば、Possible
を出力した後、 行出力せよ。 このうち 行目には、 回目の操作でほどく結び目の番号を出力せよ。 ただし、ロープ の右端とロープ の左端を結ぶものを結び目 とする。
入力例1
3 50
30 20 10
出力例1
Possible
2
1
先に結び目 をほどくと、結び目 をほどけなくなってしまいます。
入力例2
2 21
10 10
出力例2
Impossible
入力例3
5 50
10 20 30 40 50
出力例3
Possible
1
2
3
4
他に例えば、,,, の順に出力しても正解となります。