問題一覧 > 教育的問題

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

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

問題文

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

　

各非負整数 nn に対し集合 SnS_n を次の条件を満たす集合 TT 全体の集合と定めます：

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

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

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

　

SNS_N を求めてください。

入力

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

NN

制約

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

  • NN は 10610^6 以下の非負整数

出力

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

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

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

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

サンプル

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

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

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

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

2i≤12^i \leq 1 を満たす非負整数 ii は 00 のみであり、かつ 11 の二進法表記は 11 であるため、SN=S1S_N = S_1 の要素であるための条件を満たす集合 TT は S0S_0 のみとなります。サンプル1の結果を踏まえて S0={}S_0 = \{\} であるので、すなわち S1S_1 は集合 {{}}\{\{\}\} となります。

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

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

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

2i≤22^i \leq 2 を満たす非負整数 ii は 00 と 11 のみであり、かつ 22 の二進法表記は 1010 であるため、SNS_N の要素であるための条件を満たす集合 TT は S1S_1 のみとなります。サンプル2の結果を踏まえて S1={{}}S_1 = \{\{\}\} であるので、すなわち SNS_N は集合 {{{}}}\{\{\{\}\}\} となります。

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

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

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

2i≤32^i \leq 3 を満たす非負整数 ii は 00 と 11 のみであり、かつ 33 の二進法表記は 1111 であるため、SNS_N の要素であるための条件を満たす集合 TT は S0S_0 と S1S_1 のみとなります。サンプル1とサンプル2の結果を踏まえて S0={}S_0 = \{\} と S1={{}}S_1 = \{\{\}\} であるので、すなわち SNS_N は集合 {{},{{}}}\{\{\},\{\{\}\}\} となります。

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

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