#P15422. [外校精选题]小学数学

[外校精选题]小学数学

1. 小学数学

题面描述

Dozebear 是一个可爱的小学生,他非常地热爱数学,经常和周围的同学一起探讨数学问题。某一天一个比他高一级的学长给了他一道题:

你有五个水桶,分别装有 1,2,3,4,51,2,3,4,5 升的水。你每次可以选择其中两个水桶,你需要保证第一个水桶里的水不多于第二个水桶里的水,然后用第二个水桶向第一个水桶倒水,直到第一个水桶里的水量是原来的两倍。也就是说,假定原来两个水桶分别有 A,BA,B(A≤BA\le B)升的水,倒完水后两个水桶分别有 2A,B−A2A,B-A 升水。

你想要通过一系列操作,使得尽可能多的水集中在某一个水桶里。

Dozebear 看完题很快就把它秒了,并在草稿纸上写下 (1,4),(1,5),(4,1),…(1,4),(1,5),(4,1),\ldots 一系列意义不明的数对。“这个可以有!”学长看到了解题过程之后高呼。由于觉得 Dozebear 的解题过程太过精妙,学长决定请他到自己家里喝红茶,和他一起研究更难的数学问题。

喝完红茶的 Dozebear 很快就睡着了(?),在梦中他又想起了学长的数学题,他总觉得这道题能推广到更一般的情况,具体来说:

你有 nn 个水桶,第 ii 个水桶装有 ii 升的水,你需要构造一种倒水方式,使得尽可能多的水集中在一个水桶里。

Dozebear 绞尽脑汁也没能想到怎么做,你能帮帮他吗?

输入格式

一行两个正整数 n,Δn,\Delta,分别表示有多少个水桶和容许的误差。

输出格式

第一行一个数 CC,表示你的操作数。

接下来 CC 行每行两个数,用空格隔开,表示这一次操作选择的两个水桶。

假设这两个数是 xx 和 yy,你必须保证 x≠yx\ne y,并且此时 xx 桶里的水不多于 yy 桶里的水。

你的输出必须保证 C≤106C\le10^6。

输入输出样例

输入

5 1919810

输出

11
1 4
1 5
4 1
5 3
5 4
2 5
2 5
1 2
1 5
1 5
2 1

数据范围与规定

测试点编号 n=n= Δ=\Delta=
11 22 00
22 44
33 66
44 77
55 88
66 1010 10001000
77 00
88 1515 20002000
99 1616 500500
1010 1717 200200
1111 1818 00
1212 2525 50005000
1313 2727 10001000
1414 2929 500500
1515 3131 2020
1616 3333 00
1717 5050 50005000
1818 5151 20002000
1919 5252 5050
2020 5353 00
2121 9696 50005000
2222 9797 20002000
2323 9898 200200
2424 9999 1010
2525 100100 00

假设你的操作使得 X0X_0 升的水集中在某一个水桶内(SPJ 将会选取水量最多的水桶的水量作为 X0X_0),标程的解为 XX 升。如果有

X−X0≤nΔ1000,X-X_0\le\frac{n\Delta}{1000},

则你可以获得这个测试点的分数,否则令

k=1000(X−X0)nΔ−1,k=\frac{1000(X-X_0)}{n\Delta}-1,

你的这个测试点的得分是 ⌊3e−k⌋\lfloor 3e^{-k}\rfloor。

如果你的输出不合法,你将获得 00 分。