No.1255 Hairates of Bolivian
Kazun
maspyProblem Statement
For an array $\mathcal{A}=[a_1,\dots,a_N,b_1,\dots,b_N]$ with $2N$ elements, define $\pi(\mathcal{A})$ as
$\quad \pi(\mathcal{A})=[a_1,b_1,a_2,b_2,\dots,a_k,b_k,\dots,a_N,b_N]$
. Also, for a non-negative integer $n$, let
$\quad \pi^n(\mathcal{A})=\begin{cases} \pi(\pi^{n-1}(\mathcal{A})) & (n \geq 1) \\ \mathcal{A} & (n=0) \end{cases}$
.
Now, for a given positive integer $N$, let the array $\mathcal{A}$ with $2N$ elements be
$\quad \mathcal{A}=[1,2,\dots,2N-1,2N]$
. If there exists a positive integer $K$ such that $\pi^K(\mathcal{A})=\mathcal{A}$, find the smallest such positive integer; if none exists, report that fact.
Here, for 2 arrays $\mathcal{A}=[x_1,\dots,x_l], \mathcal{B}=[y_1,\dots,y_m]$, $\mathcal{A}=\mathcal{B}$ means that both of the following 2 conditions are satisfied:
- $l=m$
- For every $i=1,2,\dots,l(=m)$, $x_i=y_i$
Solve $T$ test cases.
Constraints
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^9$
- $T,N$ are integers.
Input
The input is given from standard input in the following format. Line 1 of the input is as follows.$T$Then, the following $T$ lines represent the $T$ test cases. Each of them is a line in the following format.
$N$
Output
If there exists a positive integer $K$ satisfying $\pi^K(\mathcal{A})=\mathcal{A}$, find the smallest such one. If none exists, output -1.
Sample
Sample 1
Input
3 3 2 26
Output
4 2 8
[About test case 1]
$\mathcal{A}=[1,2,3,4,5,6]$, and
$\quad \pi^{\phantom{1}}(\mathcal{A})=[1,4,2,5,3,6]$ (Correction: 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]$
Therefore, $K=4$ is the smallest positive integer satisfying $\pi^K(\mathcal{A})=\mathcal{A}$, so the correct answer is $4$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。