No.1034 テスターのふっぴーさん

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 156
作問者 : ngtkanangtkana / テスター : fuppy_kyoprofuppy_kyopro
8 ProblemId : 4021 / 出題時の順位表
問題文最終更新日: 2020-04-24 19:56:58

問題文

今から皆さんに、グリッドに関するクイズを出すフッピィ~♪ まずは初級編だピ!

テスターのふっぴーさんは、$ N \times N $ のグリッド状の市に住んでいます。 グリッドの各マスは、左上を $ ( 0, 0 ) $ とするようなお名前を持っています。 そこから、$ i $ マス下へ、$ j $ マス右へ進んだところにあるマスのお名前は、$ ( i, j ) $ です。 マス目に個性をです。これぞダイバーシティーです。(市だけに)

現在の時刻は $ 0 $ です。 テスターのふっぴーさんは、最も左上のマス $ (0, 0) $ にいます。 テスターのふっぴーさんは、はじめ右を向いています。

ここから毎回「ゲーム終了」まで、時刻の変わり目に移動をするピィ~♪ ルールを説明するピ!

  • 一度訪問したマスは二度と訪問してはいけません。
  • 四方のいずれにも未訪問のマスがなければ、そこで「ゲーム終了」です。
  • 前方(今向いている方向)にマスが存在して、未訪問ならばそこに移動です。
  • そうでないならば、前方に未訪問のマスが来るまで、時計回りに回転を繰り返して、未訪問のマスが目の前に来たらそこに移動です。

この一連の移動によって、テスターのふっぴーさんはすべてのマスを訪問して「ゲーム終了」をすることが証明できます。

例を挙げましょう。$ N = 4 $ ならば、このような順番で訪問することになります。

0 1 2 3
11 12 13 4
10 15 14 5
9 8 7 6
$ t $ と書いてあるマスは、時刻 $ t $ で訪問することになります。 例えば時刻 $ 1 $ のときには、$ ( 0, 1 ) $ となります。

さて、問題です(ピィ省略)。テスターのふっぴーさんがマス $ ( I, J ) $ を訪問するのは、時刻がいくつのときでしょうかピ!

入力

$Q$
$N_0\ I_0\ J_0$
$\cdots$
$N_{Q-1}\ I_{Q-1}\ J_{Q-1}$

この問題は、複数テストケースの問題です。 $ 1 $ 行目には、テストケースの数 $ Q $ が、一行の整数で入力されます。 $ 2 $ 行目以降の $ Q $ 行には、グリッドの一辺の長さ $ N_i $、問題のマス目の縦位置 $ I_i $、横位置 $ J_i $ が空白区切りで与えられます。

制約

  • $ 1 \leq Q \leq 100 $
  • $ 1 \leq N_i \leq 10 ^ 9 $
  • $ 0 \leq I_i < N $
  • $ 0 \leq J_i < N $

出力

$t_0$
$\cdots$
$t_{Q-1}$
各テストケースに対して、テスターのふっぴーさんが与えられたマスを訪問する時刻を、改行区切りで出力してください。 最後に改行してください。

サンプル

サンプル1
入力
1
2 1 1
出力
2

幸運なあなただけに、テスターのふっぴーさんの GPS 記録を大公開だピ!👇

0 1
3 2

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