← 返回题目列表

AtCoder · pakencamp_2018_day2_f

F. 相同的路径

中文机器翻译题面 查看原题

配点: 100 点

問題文

PAKEN 市长 E869120 在该市设立了多个检查站。2 我们计划修建几条连接两个检查站的单向道路。
检查点数量 N 和检查点 其编号为 1, 2, 3, ..., N 。

自古以来,这座城市的幸运数字就是 K 。
因此,市长决定建造一些满足以下条件的东西:

  • 检查点 到达 1 到 N 的方式正好是 无论您选择哪条路线到达 K 是的。
  • 检查点 到达 1 到 N ,您经过的道路数量将保持不变。

例如,K = 5 ,以下检查点和道路布置满足条件。因为检查站 到达 1 到 N 的方式总数为 K = 5 几乎所有方向。 3 因为它遵循书籍的路径。

出于成本考虑,市长应尽可能增加检查站的数量。 我想让 N 尽可能小。

如何构造这样的条件 1 请配置一个。但是,检查点 直接通往 a 到 b 的路是 a < b 除非是,否则不能建造,并且不得建造多条“连接相同两个检查站的道路”。 小于或等于

制約

  • K 是 1 以上 10^{18} 的整数

入力

输入是按以下格式从标准输入给出的。

K

出力

输出应采用以下格式。

N M
a_1 b_1
a_2 b_2
a_3 b_3
...
a_M b_M
  • 1 行显示检查点的数量。 N 和道路数量 请输出 M ,以空格分隔。 请通过
  • 2 从行 M 行输出道路信息。然而,a_i, b_i 是“i 第条路是检查站 “直接连接到 a_i 到 b_i ”。此时 必须是 a_i < b_i 。
  • 请在末尾添加换行符。 然而, 必须小于或等于N 是 200 。 如果不是,这是一个错误的答案。
    另外,(a_i, b_i) \neq (a_j, b_j) (i \neq j) 和 a_i < b_i 。

小課題

小課題 1 [8 点]

  • K \leq 150 满意。

小課題 2 [12 点]

  • K \leq 8 \ 000 满意。

小課題 3 [80 点]

  • 没有其他限制。

然而,小任务 对于 3 ,评分将按如下方式进行。在那里,L 对于所有测试用例 N 的最大值。 对于

  • 161 \leq L \leq 200 ,15 点
  • 152 \leq L \leq 160 ,55 - (L - 150) * 2 点
  • L = 151 ,65 点
  • L \leq 150 ,80 点満点

另外,小作业 在 1, 2 中 N \leq 200 被确定是正确的。


入力例 1

5

出力例 1

7 10
1 2
1 3
1 4
2 5
3 5
3 6
4 5
4 6
5 7
6 7

在下图中,检查点 1 到 7 我要去 5 有几种方法,都具有相同数量的方法(3 路),所以满足条件。


入力例 2

20

出力例 2

16 24
1 2
2 3
3 4
5 6
6 7
7 8
9 10
10 11
11 12
13 14
14 15
15 16
1 5
5 9
9 13
2 6
6 10
10 14
3 7
7 11
11 15
4 8
8 12
12 16

在下图中,检查点 1 到 16 我要去 20 有几种方法,都具有相同数量的方法(6 路),所以满足条件。


入力例 3

104

出力例 3

21 75
1 2
1 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
4 20
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 18
5 19
5 20
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 19
6 20
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 16
7 17
7 18
7 19
7 20
8 21
9 21
10 21
11 21
12 21
13 21
14 21
15 21
16 21
17 21
18 21
19 21
20 21

该输入是 满足 1 约束。