問題一覧 > 通常問題

No.1255 ハイレーツ・オブ・ボリビアン

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 55
作問者 : KazunKazun / テスター : maspymaspy
11 ProblemId : 4474 / 出題時の順位表
問題文最終更新日: 2020-10-09 22:47:22

問題文

要素数が $2N$ である配列 $\mathcal{A}=[a_1,\dots,a_N,b_1,\dots,b_N]$ に対して, $\pi(\mathcal{A})$ を
$\quad \pi(\mathcal{A})=[a_1,b_1,a_2,b_2,\dots,a_k,b_k,\dots,a_N,b_N]$
と定める. また, 非負整数 $n$ に対して,
$\quad \pi^n(\mathcal{A})=\begin{cases} \pi(\pi^{n-1}(\mathcal{A})) & (n \geq 1) \\ \mathcal{A} & (n=0) \end{cases}$
とする.

では, 与えられた正の整数 $N$ に対して, 要素数 $2N$ の配列 $\mathcal{A}$ を
$\quad \mathcal{A}=[1,2,\dots,2N-1,2N]$
としたとき, 正の整数 $K$ で, $\pi^K(\mathcal{A})=\mathcal{A}$ となるものが存在するならば, そのうち最小の正の整数を求め, 存在しなければ, その旨を報告せよ.

なお, 2つの配列 $\mathcal{A}=[x_1,\dots,x_l], \mathcal{B}=[y_1,\dots,y_m]$ に対して, $\mathcal{A}=\mathcal{B}$ であるとは,

  • $l=m$
  • 任意の $i=1,2,\dots,l(=m)$ に対して,$x_i=y_i$
の2つを共に満たすことである.

$T$ 個のテストケースについて答えよ.

制約

  • $1 \leq T \leq 100$
  • $1 \leq N \leq 10^9$
  • $T,N$ は整数である.

入力

入力は以下の形式で標準入力から与えられる. 入力の1行目は以下の通りである.
$T$
そして, 続く $T$ 行が $T$ 個のテストケースを表す. これらはそれぞれ以下の形式の行である.
$N$

出力

$\pi^K(\mathcal{A})=\mathcal{A}$ を満たす正の整数 $K$ が存在すれば, そのうち最小のものを求めよ. 存在しなければ-1を出力せよ.

サンプル

サンプル1
入力
3
3
2
26
出力
4
2
8

[第1テストケースについて]
$\mathcal{A}=[1,2,3,4,5,6]$ であり,
$\quad \pi^{\phantom{1}}(\mathcal{A})=[1,4,2,5,3,6]$ (訂正:2020/10/09 22:46 $\mathcal{L} \to \mathcal{A}$)
$\quad \pi^2(\mathcal{A})=[1,5,4,3,2,6]$
$\quad \pi^3(\mathcal{A})=[1,3,5,2,4,6]$
$\quad \pi^4(\mathcal{A})=[1,2,3,4,5,6]$
より, $K=4$ が $\pi^K(\mathcal{A})=\mathcal{A}$ を満たす最小の正の整数なので, 正解は $4$ である.

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