No.1255 ハイレーツ・オブ・ボリビアン
タグ : / 解いたユーザー数 70
作問者 : 👑
Kazun
/ テスター :
maspy
問題文
要素数が $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$
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。