問題一覧 > 教育的問題

No.2118 Enumeration of Hereditarily Finite Sets

レベル : / AI推定難易度 : 312 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 86
作問者 : 👑 p-adic / テスター : MasKoaTS
お気に入りにしたユーザー ProblemId : 8531 / 自分の提出
問題文最終更新日: 2022-10-10 10:27:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 367 (順位表) の他の問題:

Problem Statement

A non-negative integer $N$ is given as input.

 

For each non-negative integer $n$, define the set $S_n$ as the set of all sets $T$ satisfying the following condition:

  • There exists a non-negative integer $i$ satisfying all of the following $3$ conditions:
    1. $2^i \leq n$. (Hence the $2^i$'s place in the binary representation of $n$ is meaningful.)
    2. The $2^i$'s place (the $1+i$-th digit) in the binary representation of $n$ is $1$.
    3. $T = S_i$.

At first glance, this may look like circular reasoning, since $S_i$ is used in the definition of $S_n$. However, the definition of $S_n$ does not use $S_n$ itself, but only $S_i$ for non-negative integers $i$ satisfying $2^i \leq n$ (which are therefore at most $\log_2 n$ and strictly smaller than $n$), so no circular reasoning occurs. See the samples for details.

Such a definition is called a recursive definition, and it appears in many situations in mathematics and programming.

 

Find $S_N$.

Input

The input is given from standard input in the following format:

$N$

Constraints

The input satisfies the following constraints:

  • $N$ is a non-negative integer not exceeding $10^6$

Output

Output $S_N$ on $1$ line, followed by a newline. When outputting a set, follow the procedure below:

  • First, output a half-width left curly brace {.
  • Next, output all of its elements in any order, separated by half-width commas ,, without duplicates.
  • Then, output a half-width right curly brace }.

For example, to output the empty set $\{\}$, first output {, then output nothing since there are no elements, and then output }. Thus, in the end, you output {}.

This problem uses a special judge. There is not necessarily only $1$ correct answer, but output just $1$ of them.

Sample

Sample 1
Input
0
Output
{}

Since there is no non-negative integer $i$ satisfying $2^i \leq 0$, there is no set $T$ satisfying the condition for being an element of $S_N = S_0$. That is, $S_0$ is the empty set $\{\}$.

To output the empty set $\{\}$, as explained in the output format, first output {, then output nothing since there are no elements, and then output }. Thus, in the end, you output {}.

Sample 2
Input
1
Output
{{}}

The only non-negative integer $i$ satisfying $2^i \leq 1$ is $0$, and the binary representation of $1$ is $1$, so the only set $T$ satisfying the condition for being an element of $S_N = S_1$ is $S_0$. From the result of Sample 1, $S_0 = \{\}$, so $S_1$ is the set $\{\{\}\}$.

To output the set $\{\{\}\}$, first output {, then, since the only element is $\{\}$, output {} based on the result of Sample 1, and then output }. Thus, in the end, you output {{}}.

Note that elements must be output without duplicates, so outputting {{},{}} or {{},{},{}} results in WA.

Sample 3
Input
2
Output
{{{}}}

The only non-negative integers $i$ satisfying $2^i \leq 2$ are $0$ and $1$, and the binary representation of $2$ is $10$, so the only set $T$ satisfying the condition for being an element of $S_N$ is $S_1$. From the result of Sample 2, $S_1 = \{\{\}\}$, so $S_N$ is the set $\{\{\{\}\}\}$.

To output the set $\{\{\{\}\}\}$, first output {, then, since the only element is $\{\{\}\}$, output {{}} based on the result of Sample 2, and then output }. Thus, in the end, you output {{{}}}.

Note that elements must be output without duplicates, so outputting {{{}},{{}}} or {{{}},{{}},{{}}} results in WA.

Sample 4
Input
3
Output
{{},{{}}}

The only non-negative integers $i$ satisfying $2^i \leq 3$ are $0$ and $1$, and the binary representation of $3$ is $11$, so the only sets $T$ satisfying the condition for being an element of $S_N$ are $S_0$ and $S_1$. From the results of Sample 1 and Sample 2, $S_0 = \{\}$ and $S_1 = \{\{\}\}$, so $S_N$ is the set $\{\{\},\{\{\}\}\}$.

To output the set $\{\{\},\{\{\}\}\}$, first output {, then, since the only elements are $\{\}$ and $\{\{\}\}$, output {} and {{}} in any order, separated by a half-width comma ,, based on the results of Sample 1 and Sample 2, and then output }. Thus, in the end, you output {{},{{}}} or {{{}},{}}.

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