問題一覧 > 教育的問題

No.2118 遺伝的有限集合の数え上げ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 82
作問者 : 👑 p-adicp-adic / テスター : MasKoaTSMasKoaTS
0 ProblemId : 8531 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-10 10:27:10

問題文

入力に非負整数 $N$ が与えられます。

　

各非負整数 $n$ に対し集合 $S_n$ を次の条件を満たす集合 $T$ 全体の集合と定めます：

  • 以下の $3$ 条件を全て満たす 非負整数 $i$ が存在する：
    1. $2^i \leq n$ である。（従って $n$ の二進法表記における $2^i$ の位が意味を持つ）
    2. $n$ の二進法表記における $2^i$ の位（$1+i$ 桁目）が $1$ である。
    3. $T = S_i$ である。

一見すると $S_n$ の定義で $S_i$ が使われていて循環論法を起こしているようですが、 $S_n$ の定義で使われているのは $S_n$ そのものではなく $2^i \leq n$ を満たす（従って $\log_2 n$ 以下であり $n$ より真に小さい）非負整数 $i$ に対する $S_i$ だけであるため循環論法は生じません。詳しくはサンプルを確認してください。

このような定義は再帰的定義と呼ばれ、数学やプログラミングの様々な局面で現れます。

　

$S_N$ を求めてください。

入力

入力は次の形式で標準入力から与えられます： 

$N$

制約

入力は以下の制約を満たします：

  • $N$ は $10^6$ 以下の非負整数

出力

$S_N$ を $1$ 行に出力し、最後に改行してください。ただし集合を出力する際は以下の手順に従ってください：

  • まず、半角左波カッコ{を出力する。
  • 次に、その全ての要素を好きな順に半角コンマ,区切りで重複なく出力する。
  • その後、半角右波カッコ}を出力する。

例えば空集合 $\{\}$ を出力するには、まず{を出力し、次に要素はないので何も出力せず、その後}を出力することになります。従って結局{}を出力することになります。

なおこの問題はスペシャルジャッジ問題です。正解は $1$ 通りと限りませんが、$1$ つだけ出力してください。

サンプル

サンプル1
入力
0
出力
{}

$2^i \leq 0$ を満たす非負整数 $i$ は存在しないため、$S_N = S_0$ の要素であるための条件を満たす集合 $T$ は存在しません。すなわち $S_0$ は空集合 $\{\}$ となります。

空集合 $\{\}$ を出力するには、出力フォーマットで説明したようにまず{を出力し、次に要素はないので何も出力せず、その後}を出力することになります。従って結局{}を出力することになります。

サンプル2
入力
1
出力
{{}}

$2^i \leq 1$ を満たす非負整数 $i$ は $0$ のみであり、かつ $1$ の二進法表記は $1$ であるため、$S_N = S_1$ の要素であるための条件を満たす集合 $T$ は $S_0$ のみとなります。サンプル1の結果を踏まえて $S_0 = \{\}$ であるので、すなわち $S_1$ は集合 $\{\{\}\}$ となります。

集合 $\{\{\}\}$ を出力するには、まず{を出力し、次に要素は $\{\}$ だけなのでサンプル1の結果を踏まえて{}を出力し、その後}を出力することになります。従って結局{{}}を出力することになります。

なお要素を重複させずに出力するよう指定されているので、{{},{}}や{{},{},{}}を出力してしまうと WA となってしまいます。

サンプル3
入力
2
出力
{{{}}}

$2^i \leq 2$ を満たす非負整数 $i$ は $0$ と $1$ のみであり、かつ $2$ の二進法表記は $10$ であるため、$S_N$ の要素であるための条件を満たす集合 $T$ は $S_1$ のみとなります。サンプル2の結果を踏まえて $S_1 = \{\{\}\}$ であるので、すなわち $S_N$ は集合 $\{\{\{\}\}\}$ となります。

集合 $\{\{\{\}\}\}$ を出力するには、まず{を出力し、次に要素は $\{\{\}\}$ だけなのでサンプル2の結果を踏まえて{{}}を出力し、その後}を出力することになります。従って結局{{{}}}を出力することになります。

なお要素を重複させずに出力するよう指定されているので、{{{}},{{}}}や{{{}},{{}},{{}}}を出力してしまうと WA となってしまいます。

サンプル4
入力
3
出力
{{},{{}}}

$2^i \leq 3$ を満たす非負整数 $i$ は $0$ と $1$ のみであり、かつ $3$ の二進法表記は $11$ であるため、$S_N$ の要素であるための条件を満たす集合 $T$ は $S_0$ と $S_1$ のみとなります。サンプル1とサンプル2の結果を踏まえて $S_0 = \{\}$ と $S_1 = \{\{\}\}$ であるので、すなわち $S_N$ は集合 $\{\{\},\{\{\}\}\}$ となります。

集合 $\{\{\},\{\{\}\}\}$ を出力するには、まず{を出力し、次に要素は $\{\}$ と $\{\{\}\}$ だけなのでサンプル1とサンプル2の結果を踏まえて{}と{{}}を好きな順に半角コンマ,区切りで出力し、その後}を出力することになります。従って結局{{},{{}}}か{{{}},{}}を出力することになります。

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