#P9328. [CCC 2023 S5] The Filter
[CCC 2023 S5] The Filter
题目描述
Alice, the mathematician, likes to study real numbers that are between and . Her favourite tool is the filter.
A filter covers part of the number line. When a number reaches a filter, two events can happen. If a number is not covered by the filter, the number will pass through. If a number is covered, the number will be removed.
Alice has infinitely many filters. Her first filters look like this:
In general, the filter can be defined as follows:
-
Consider the number line from to .
-
Split this number line into equal-sized pieces. There are points and intervals.
-
The filter consists of the interval, interval, interval, and in general, the interval. The points are not part of the filter.
Alice has instructions for constructing the Cantor set. Start with the number line from to . Apply all filters on the number line, and remove the numbers that are covered. The remaining numbers form the Cantor set.
Alice wants to research the Cantor set, and she came to you for help. Given an integer , Alice would like to know which fractions are in the Cantor set.
输入格式
The first line contains the integer .
The following table shows how the available marks are distributed.
Marks | Bounds on | Additional Constraints |
---|---|---|
marks | is a power of . | |
marks | None. | |
marks |
输出格式
Output all integers where and is in the Cantor set.
Output the answers in increasing order. The number of answers will not exceed .
12
0
1
3
4
8
9
11
12
提示
are not in the Cantor set because they were covered by the 1st filter. Furthermore, and are not in the Cantor set because they were covered by the filter.
It can be shown that the remaining fractions will pass through all filters.
本题采用捆绑测试:
-
Subtask 1(3 points):, 是 的整数次幂。
-
Subtask 2(4 points):。
-
Subtask 3(8 points):。