問題一覧 > 通常問題

No.471 直列回転機

レベル : / 実行時間制限 : 1ケース 3.141秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 52
作問者 : koyumeishi / テスター : tubo28
3 ProblemId : 709 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-01-23 00:46:41

問題文

平面上の点を 点P(px,py) を中心に反時計回りに R度 (R{0,90,180,270}) 回転させる機械を回転機と言います。
N機の回転機があり、 回転機iは平面上の点を 点Pi(pix,piy) を中心に反時計回りに Ri度 (Ri{0,90,180,270}) 回転させます。

M個の点の座標が与えられるので、回転機1から回転機Nまで番号順に続けて使用した後の点の座標を出力してください。
(点を回転機1で回転 -> 更に回転機2で回転 -> -> 更に回転機Nで回転)

というのはよくある問題なので、一捻りします。
回答者に回転機の情報は与えられません。 その代わり10回まで 点(x,y) ( x,y は整数 かつ |x|,|y|104 ) にN機の回転機を使用した後の座標 (x,y) を返す質問クエリを実行することができます。

入出力

この問題はリアクティブ問題です。 出力の flush を忘れないでください。

標準入力にM個の点が与えられるので、まずはこれを受け取ってください。 入力は全て整数で与えられます。

M
x1 y1

xM yM

1M5×104
|xi|,|yi|104

入力を受け取ったら、質問クエリ、解答クエリを実行してください。

質問クエリは、次のフォーマットで標準出力へ出力してください。 末尾に改行が必要です。

? x y

質問クエリは10回まで実行できます。 10回を超えると不正解となります。
x,y は整数 かつ |x|,|y|104 である必要があります。 (制約を満たさない場合、ジャッジプログラムが正常に動作しない場合があります)

質問クエリに対する応答は、次のフォーマットで標準入力へ返されます。

x y

質問クエリで与えられた 点(x,y)N 機の回転機で回転した後の座標 (x,y) が返されます。 x,y は整数ですが、入力次第では 104 を超える場合があります。

質問クエリを行った後、解答クエリを次のフォーマットで出力してください。

!
x1 y1

xM yM

1行目には "!", 2行目以降には最初に与えられたM個の点を回転させた後の点を一行ずつ順に出力してください。
全ての点に関して正しいと判定されると正解となります。 後ろに余計な出力はしないでください。

また回答者には開示されませんが、 N機の回転機は以下の形式でジャッジに与えられています。

N
p1x p1y R1

pNx pNy RN

1N5×104
|pix|,|piy|104
Ri{0,90,180,270}

サンプル

サンプル1

回転機が次のような場合です。

2
0 0 90
1 1 90

平面上の点は (0,0) を中心に 90度回転させられた後、 (1,1) を中心に 90度回転させられます。
例) (1,1) -> (-1,1) -> (1,-1)

入力

初めに M 個の点についての情報を受け取ってください。

3
0 0
1 0
1 1

質問クエリを10回まで行うことが出来ます。 以下はその一例です。

質問

? 0 0

応答

2 0

質問

? 1 0

応答

1 0

質問

? 1 1

応答

1 -1

解答クエリ

!
2 0
1 0
1 -1

M>10 のケースに対してこの手法は使えないので、工夫したり超能力を使ったりして解いてください。

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