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