CF1408F Two Different
You are given an integer .
You should find a list of pairs () satisfying the following condition.
Let’s consider some function (we define as the set of positive integers). In other words, is a function that returns a positive integer for a pair of positive integers.
Let’s make an array , where initially.
You will perform operations, in -th of them you will:
-
assign ( is a temporary variable, it is used only for the next two assignments);
-
assign ;
-
assign .
In other words, you need to simultaneously change and to . Note that during this process is always the same for a fixed pair of and .
In the end, there should be at most two different numbers in the array a.
It should be true for any function .
Find any possible list of pairs. The number of pairs should not exceed .
Input
The single line contains a single integer ().
Output
In the first line print () — the number of pairs.
In each of the next lines print two integers. In the -th line print ().
The condition described in the statement should be satisfied.
If there exists multiple answers you can print any of them.
Examples
input
1 | 3 |
output
1 | 1 |
input
1 | 4 |
output
1 | 2 |
Note
In the first example, after performing the only operation the array will be . It will always have at most two different numbers.
In the second example, after performing two operations the array will be . It will always have at most two different numbers.
Translation
定义二元函数 ,定义域为正整数对,值域为正整数,映射方式未知。自变量相同的时候保证函数值相同。
给一个长度为 的序列 ,初始时 。每次可以选择两个数
$x_ i , y_ i ∈ [ 1 , n ] $,令 ,你需要构造一个操作顺序使得不论 函数如何定义,最终操作的结果都能使序列中不相同数的个数不超过 。
Idea
那么不妨考虑四个数的情况.
先操作 ,再操作 ,然后操作 和 ,此时四个数完全一样。类似的,,长度为 的序列,都能经过若干次操作变成同一数值。下面用数学归纳法证明:当 时,操作 ,显然成立;假设当 时上述命题成立;那么当 时,首先将序列前 个数变为 ,再将序列后 个数字变成 ,接着依次操作 ,其中 且 ,最终将所有数字变成 ,证毕。
令 表示序列长度为 时,将所有数字变为同一数值的操作次数。那么有 ,且 ,得 。
对于长度为 的序列,取 为使得 的最大正整数。我们先用 步把前 个数字变成 ,再用 步把后 个数字变为 。由于 ,最终序列只会包含 和 。
由于 ,故 的最大值为 ,最大操作次数为 ,满足条件。
采用递归分治法求得方案。
Code
1 | /****************************************************************** |