Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
この問題はインタラクティブな問題(あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題)です。
N 個のおもりが手元にあります。i 番目のおもりの重さを P_i としたとき、(P_1, \dots, P_N) は (1, \dots, N) の順列となることが分かっていますが、P_i の具体的な値は分かっていません。 また、-2N 以上 2N 以下の整数の目盛りがついた棒が、位置 0 のところでつるされています。目盛りがついている位置には穴が開いており、それぞれの穴には 1 個までおもりをぶら下げることができます。 はじめはおもりが 1 つもぶら下がっておらず、棒はつりあっています。
zkou くんは最終的に、手元にある N 個のおもりをすべて棒にぶら下げて、なおかつ棒をつりあわせたいです。 あなたは zkou くんに以下のいずれかの操作をするよう指示できます。
- 手元にあるおもりを 1 つ選び、おもりがまだぶら下がっていない穴にぶら下げる。
- 棒にぶら下がっているおもりを 1 つ選び、手元に戻す。
zkou くんは操作を終えるたびに、棒が左右どちらに傾いたか、あるいはつりあったかを、あなたに伝えます。 10000 回以下の指示で、手元にある N 個のおもりをすべて棒にぶら下げて、なおかつ棒をつりあわせてください。 なお、制約下で常につりあわせる方法が存在することが証明できます。
棒の傾きとつりあいについて
棒に k 個のおもりがのっていて、j 番目のおもりが重さ w_j で位置 x_j にあるとき、棒のモーメント M を M = \sum_{j = 1}^{k} w_j x_j と定義します。M > 0 なら棒が右に傾き、M = 0 なら棒はつりあい、M < 0 なら棒が左に傾きます。制約
- 入力は全て整数
- 1 \leq N \leq 3000
部分点
- 1 \leq N \leq 100 を満たすデータセットに正解した場合は 30 点が与えられる。
入出力
この問題はインタラクティブな問題(あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題)です。
最初に、N を標準入力から受け取ってください。
N
次に、手元にある N 個のおもりをすべて棒にぶら下げて、なおかつ棒をつりあわせるまで、zkou くんに操作を指示できます。その際、以下の形式で標準出力に出力してください。
手元にある i 番目のおもりを選び、おもりがまだぶら下がっていない位置 x の穴にぶら下げるとき:
1 i x
ここで、i, x は 1\leq i\leq N, -2N\leq x\leq 2N を満たす整数である必要があります。
棒にぶら下がっている i 番目のおもりを手元に戻すとき:
2 i
ここで、i は 1\leq i\leq N を満たす整数である必要があります。
この指示への返答は以下の形式で標準入力から与えられます。
S
ここで、S は以下のいずれかの文字列です。
Right
:棒は操作後に右に傾いた。Balanced
:棒は操作後につりあった。Left
:棒は操作後に左に傾いた。-1
:不正な出力が行われた。
-1
が入力に与えられた場合、すぐにプログラムを終了してください。出力が不正とみなされる原因の例としては、以下が挙げられます。
- 出力の形式が異なっていた。
- 指示回数が上限を超えた。
- 既に棒にぶら下がっているおもりを棒にぶら下げる指示を出した。
- 手元にあるおもりを手元に戻す指示を出した。
- 既におもりがぶら下がっている穴に別のおもりをぶら下げる指示を出した。
N
個のおもりをすべて棒にぶら下げて、なおかつ棒をつりあわせることができたら、以下の形式で
0
を標準出力に出力し、プログラムを終了してください。N
個のおもりがすべて棒にぶら下がっており、なおかつ棒がつりあっている場合、AC
となります。
0
注意点
- 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
- 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
-
答えを出力したら(または
-1
を受け取ったら)直ちにプログラムを正常終了してください。そうしなかった場合、ジャッジ結果は不定です。 - 特に、余計な改行や空白の出力も不正なフォーマットの出力とみなされるので注意してください。
入出力例
以下は N = 2 かつ (P_1, P_2) = (2, 1) の場合の入出力例です。
入力 | 出力 | 説明 |
---|---|---|
2 |
N が与えられます。 | |
1 2 -4 |
2 番目のおもりを位置 -4 にぶら下げます。 | |
Left |
棒は左に傾きました。 | |
1 1 3 |
1 番目のおもりを位置 3 にぶら下げます。 | |
Right |
棒は右に傾きました。 | |
2 1 |
1 番目のおもりを手元に戻します。 | |
Left |
棒は左に傾きました。 | |
1 1 2 |
1 番目のおもりを位置 2 にぶら下げます。 | |
Balanced |
棒はつりあいました。 | |
0 |
おもりをすべて棒にぶら下げつつ棒をつりあわせました。0
を出力してプログラムを終了してください。
|