1. 小学数学
题面描述
Dozebear 是一个可爱的小学生,他非常地热爱数学,经常和周围的同学一起探讨数学问题。某一天一个比他高一级的学长给了他一道题:
你有五个水桶,分别装有 1,2,3,4,5 升的水。你每次可以选择其中两个水桶,你需要保证第一个水桶里的水不多于第二个水桶里的水,然后用第二个水桶向第一个水桶倒水,直到第一个水桶里的水量是原来的两倍。也就是说,假定原来两个水桶分别有 A,B(A≤B)升的水,倒完水后两个水桶分别有 2A,B−A 升水。
你想要通过一系列操作,使得尽可能多的水集中在某一个水桶里。
Dozebear 看完题很快就把它秒了,并在草稿纸上写下 (1,4),(1,5),(4,1),… 一系列意义不明的数对。“这个可以有!”学长看到了解题过程之后高呼。由于觉得 Dozebear 的解题过程太过精妙,学长决定请他到自己家里喝红茶,和他一起研究更难的数学问题。
喝完红茶的 Dozebear 很快就睡着了(?),在梦中他又想起了学长的数学题,他总觉得这道题能推广到更一般的情况,具体来说:
你有 n 个水桶,第 i 个水桶装有 i 升的水,你需要构造一种倒水方式,使得尽可能多的水集中在一个水桶里。
Dozebear 绞尽脑汁也没能想到怎么做,你能帮帮他吗?
输入格式
一行两个正整数 n,Δ,分别表示有多少个水桶和容许的误差。
输出格式
第一行一个数 C,表示你的操作数。
接下来 C 行每行两个数,用空格隔开,表示这一次操作选择的两个水桶。
假设这两个数是 x 和 y,你必须保证 x=y,并且此时 x 桶里的水不多于 y 桶里的水。
你的输出必须保证 C≤106。
输入输出样例
输入
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= |
Δ= |
| 1 |
2 |
0 |
| 2 |
4 |
| 3 |
6 |
| 4 |
7 |
| 5 |
8 |
| 6 |
10 |
1000 |
| 7 |
0 |
| 8 |
15 |
2000 |
| 9 |
16 |
500 |
| 10 |
17 |
200 |
| 11 |
18 |
0 |
| 12 |
25 |
5000 |
| 13 |
27 |
1000 |
| 14 |
29 |
500 |
| 15 |
31 |
20 |
| 16 |
33 |
0 |
| 17 |
50 |
5000 |
| 18 |
51 |
2000 |
| 19 |
52 |
50 |
| 20 |
53 |
0 |
| 21 |
96 |
5000 |
| 22 |
97 |
2000 |
| 23 |
98 |
200 |
| 24 |
99 |
10 |
| 25 |
100 |
0 |
假设你的操作使得 X0 升的水集中在某一个水桶内(SPJ 将会选取水量最多的水桶的水量作为 X0),标程的解为 X 升。如果有
X−X0≤1000nΔ,
则你可以获得这个测试点的分数,否则令
k=nΔ1000(X−X0)−1,
你的这个测试点的得分是 ⌊3e−k⌋。
如果你的输出不合法,你将获得 0 分。