問題一覧 > 通常問題

No.282 おもりと天秤(2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 256 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 72
作問者 : 紙ぺーぱー紙ぺーぱー
17 ProblemId : 721 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:56

問題文

授業中にもかかわらず遊んでしまうdaveは、
理科の実験中に、色んな重さの種類があるおもりをすべて使って、
ちょうど天秤が水平になるおもりの組み合わせがあるかを知りたくなったようで、それに遊び呆けてる。
水平になるおもりの組み合わせがあるかどうかは分かったものの、おもりの重さが分からなくなってしまいおもりと天秤を片付けられなくなったdaveは途方に暮れている。
あなたはdaveのためにおもりを重さの昇順に並べてあげて、授業に集中させるようにしてください。


$N$個の重さが互いに異なるおもりと$N$個の天秤があります。
おもりと天秤にはそれぞれ$1$から$N$の番号がふられています。
おもりの重さは0より大きいことが保証されています。
あなたは2つのおもりの重さを天秤で調べることができます。
天秤を使っておもりの関係を調べて、おもりを重さの昇順に並べましょう。

ただし、天秤の操作は$2000$回までしかできないものとする。(2015/09/19 10:40追記)

入出力

おもりと天秤の数$N(1 \le N \le 500)$が最初の1行に与えられる。
あなたが提出したプログラム(以下、回答プログラムとする)は2種類のクエリを標準出力に出力しなければならない。
クエリは天秤におもりをのせ,重さを比較する質問クエリと、おもりを重さの昇順に並べる回答クエリである。
質問クエリのフォーマットは

$?$ $L_1$ $R_1$ ... $L_N$ $R_N$
であり、回答クエリのフォーマットは
$!$ $A_1$ $A_2$ ... $A_N$
である。
$L_i$は$i$番目の天秤の左側に載せるおもりの番号、$R_i$は$i$番目の天秤の右側に載せるおもりの番号である。なにも載せない場合は0を出力せよ。
あるおもりを2ヶ所に載せることや、1ヶ所に2つのおもりを載せることはできないものとする。すなわち,"$?$ $1$ $2$ $1$ $3$"や"$?$ $1$ $1$ $1$ $1$"は不正な出力としてみなされる。
$A_i$は$i$番目に軽いおもりの番号を表す。

各クエリは、1行に出力してください。改行を忘れないこと。
質問クエリを行うと、回答プログラムの標準入力に結果が返される。
結果のフォーマットは
$C_1$ $C_2$ ... $C_N$
である。
$C_i$は天秤の傾きであり、$i$番目の天秤が左側に傾いたとき'$>$'が、つりあっているならば'$=$'が、右側に傾いたならば'$<$'が入力される。
天秤は重いおもりが載っている方に傾くものとする。天秤は理想的なものであり、誤差などはない。
詳しくはサンプルを確認すること。

出力後に、出力をflushせよ。flushしなかった場合、応答プログラムが入力を処理できず制限時間を超えてしまい、その結果不正解となることがある。また、質問クエリの実行後必ずその結果を受け取ること。応答プログラムが入力を処理できず不正解の原因となることがある。

回答クエリの実行後、プログラムをただちに終了すること。ジャッジの制限時間を超えた結果として不正解となることがある。
この問題はスペシャルジャッジである。ジャッジの制限時間以内に終了し、質問回数が$2000$回以下であり(2015/09/19 10:40追記)、回答クエリが出力したおもりが重さの昇順に並んでいた場合正解とみなされる。

注意点

  • ジャッジの制限時間は5秒としているが、応答プログラムの反応時間をも含めている。
  • 2種類のクエリ以外の出力を行った場合は不正解となる。
  • 標準エラー出力への出力は質問クエリとも回答クエリとも不正な出力ともみなされない。
  • 質問クエリの回数には制限がある(2015/09/19 10:40追記)
  • おもりの重さは互いに異なる(2015/09/19 11:06追記)

プログラムの例
import sys
n = int(input())
print ("? 1 2 0 0")
sys.stdout.flush()
if input() == "> =":
    print("! 2 1")
else:
    print("! 1 2")
sys.stdout.flush()

サンプル

サンプル1
入力
2
> =
出力
? 1 2 0 0
! 2 1

2個のおもりがあることが与えられた。
1番目の天秤の左側に1番目のおもりを、右側に2番目のおもりを載せた。2番目の天秤にはおもりを載せないことにした。 比較を行った結果1番目のおもりが2番目のおもりより重いことがわかった。
おもりを重さの昇順で並べたところ、"2 1"となると回答した。
1番目のおもりが2番目のおもりより重いので正解である。

サンプル2
入力
3
> > =
< > =
> > >
= = =
< < <
出力
? 1 2 3 0 0 0
? 1 3 2 0 0 0
? 1 0 2 0 3 0
? 0 0 0 0 0 0
? 0 1 0 2 0 3
! 2 1 3

何も載せていない天秤同士はつりあう。
片側にのみおもりを載せた場合、そちらに傾く。
天秤におもりを1つも載せずに質問を行うことは不正な出力ではない。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。