問題一覧 > 通常問題

No.1528 Not 1

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 158
作問者 : PCTprobabilityPCTprobability / テスター : tatyamtatyam hamamuhamamu
0 ProblemId : 6361 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-04 19:37:16

問題文

以下を満たす長さ $\displaystyle \left\lceil \frac{N}{2} \right\rceil$ の正整数列 $A_1,A_2,...,A_{\left\lceil \frac{N}{2} \right\rceil}$ を構築してください。条件を満たす数列が存在しない場合はそのことを報告してください。

  • $1 \le A_i \le N$
  • $i \neq j$ ならば $A_i \neq A_j$
  • $\mathrm{gcd}(A_i,A_{i+1}) \neq 1\ (1 \le i \le \displaystyle \left\lceil \frac{N}{2} \right\rceil -1)$

ただし、 $\displaystyle \lceil x \rceil$ は 実数 $x$ 以上の最小の整数のことを表します。

入力

$N$

  • 入力は全て整数である。
  • $1 \le N \le 2 \times 10^5$

出力

条件を満たす正整数列が存在しないならば $-1$ を出力してください。

条件を満たす正整数列が存在するならば以下のように、条件を満たす数列を空白区切りで出力してください。

解が複数存在する場合はいずれを出力しても構いません。

$A_1\ A_2\ \dots\ A_{\left\lceil \frac{N}{2} \right\rceil}$

サンプル

サンプル1
入力
11
出力
3 9 6 2 10 5

全ての要素が $11$ 以下かつ異なり、$\mathrm{gcd}(3,9)=3,\mathrm{gcd}(9,6)=3,\mathrm{gcd}(6,2)=2,\mathrm{gcd}(2,10)=2,\mathrm{gcd}(10,5)=5$ より条件を満たします。

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