問題一覧 > 通常問題

No.1114 足し算盆に返らず

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 271
作問者 : 37zigen37zigen / テスター : Kiri8128Kiri8128
4 ProblemId : 4703 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-22 17:25:00

問題文

$\{1,\ldots,N\}$ の$n$元部分集合 $\{a_1,\ldots,a_n\}$ が任意の$i,j,k$ ($1 \leq i,j,k \leq n$) について $a_i+a_j \neq a_k$ を満たすとする。
このような $\{a_i\}$ のうち、$n$が最大であるものを構成せよ。

入力

$N$

$1\leq N \leq 10^5$

出力

$a_1$ $a_2$ $\ldots$ $a_n$
$n$が最大となる $\{a_i\}$ を出力せよ。構成が複数存在する場合はいずれでも良い。

サンプル

サンプル1
入力
1
出力
1

サンプル2
入力
2
出力
1

$\{1,2\}$ は $1+1=2$ より不適。

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