No.2118 Enumeration of Hereditarily Finite Sets
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:
- $2^i \leq n$. (Hence the $2^i$'s place in the binary representation of $n$ is meaningful.)
- The $2^i$'s place (the $1+i$-th digit) in the binary representation of $n$ is $1$.
- $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もしくは右上の雲マークをクリックしてアカウントを作成してください。
MasKoaTS