NOIp Senior Day1
zhzh2001
题目名称 阶乘 激光和镜子 干草堆猜测
目录 fact lasers bales
可执行文件名 fact lasers bales
输入文件名 fact.in lasers.in bales.in
输出文件名 fact.out lasers.out bales.out
时间限制 1s 1s 1s
空间限制 512MB 512MB 512MB
测试点数量 20 20 20
测试点分数 5 5 5
比较方式 SPJ 全文 全文
部分分 有 无 无
提交源程序文件名
对于 C++ 语言 fact.cpp lasers.cpp bales.cpp
对于 C 语言 fact.c lasers.c bales.c
对于 Pascal 语言 fact.pas lasers.pas bales.pas
编译选项
对于 C++ 语言 -O2 -std=gnu++11 -O2 -std=gnu++11 -O2 -std=gnu++11
对于 C 语言 -O2 -O2 -O2
对于 Pascal 语言 -O2 -O2 -O2
注意事项：
1. 注意编译选项，避免未定义行为或编译错误。
2. 代码长度限制为 100KB。
3. 注意代码常数和 I/O 造成的效率影响。
1
1 阶乘 (FACT.CPP/C/PAS) 2
1 阶乘 (fact.cpp/c/pas)
1.1 题目描述
定义 n! =
∏
n
i=1
n ∀n ≥ 1。请求出 n!(1 ≤ n ≤ 1, 000, 000, 000) 的近似值，保留 k
位 (k ≤ 10) 有效数字。
1.2 输入格式 (fact.in)
两个整数 n, k。
1.3 输出格式 (fact.out)
一个用科学记数法表示的答案，格式为d.ddddde+dddd，其中 d 表示数字。当然，实
际的长度与 n 和 k 有关。不要输出末尾的 0，如果没有小数部分，不要输出小数点。
1.4 输入样例
10 4
1.5 输出样例
3.629e+6
1.6 样例解释
10! = 3, 628, 800 ≈ 3.629 ∗ 10
6
1 阶乘 (FACT.CPP/C/PAS) 3
1.7 数据范围
测试点 n k
1 ≤ 20
≤ 6
2 ≤ 100
3 ≤ 150
4 ≤ 500
5 ≤ 1, 000
6 ≤ 1, 500
7 ≤ 2, 000
8 ≤ 3, 000
9 ≤ 5, 000
10 ≤ 10, 000
11 ≤ 50, 000
12 ≤ 3, 000, 000
13 ≤ 10, 000, 000
14
≤ 1, 000, 000
≤ 7
15 ≤ 8
16
≤ 100, 000, 000
≤ 9
17
≤ 10
18 ≤ 200, 000, 000
19 ≤ 500, 000, 000
20 ≤ 1, 000, 000, 000
1.8 部分分
• 如果你的答案格式错误，不得分
• 如果你的答案格式正确，并且 e 前的部分完全正确，得到测试点 60% 的分数
• 如果你的答案格式正确，并且 e 后的部分完全正确，得到测试点 40% 的分数
2 激光和镜子 (LASERS.CPP/C/PAS) 4
2 激光和镜子 (lasers.cpp/c/pas)
2.1 题目描述
因为一些原因，农夫约翰的奶牛总是喜欢进行激光展示。
为了它们最新的展示，奶牛们已经取得了一个巨大而强大的激光源——它是如此的
巨大，实际上，以至于它们看起来不能轻松的把它从交付的地方移动。它们想找到一种
方法把激光从光源处发送到在另一边的牛棚。光源和牛棚可以看成在二维平面上的点。
奶牛们打算旋转光源使其沿水平或竖直方向发出一束光 (也就是和 x 轴或 y 轴平行)。
它们将会通过一些镜子反射激光，使其重定向到牛棚。
在农场上有 N 个不同 的栅栏柱 (1 ≤ N ≤ 300, 000) 在二维平面上 (不同于光源和
牛棚)，奶牛可以把镜子挂载在栅栏柱上面。奶牛也可以选择不在一个栅栏柱上挂载镜
子，这种情况下激光将会简单地直接从上面通过而不改变方向。如果奶牛在栅栏柱上挂
载了镜子，它们可以把镜子对齐像/或\，这样它将会把一束水平的光重定向为竖直方向，
反之亦然。
请计算奶牛最少 需要多少镜子来把激光重定向到牛棚，数据保证有解。
2.2 输入格式 (lasers.in)
第一行包含五个整数 N, x
L
, y
L
, x
B
, y
B
，其中 (x
L
, y
L
) 是光源所在的位置，(x
B
, y
B
)
是牛棚所在的位置。所有的坐标都在 0 到 1,000,000,000 之间。
接下来 N 行，每行包含一个栅栏柱的坐标，也在 0 . . . 1, 000, 000, 000 范围内。
2.3 输出格式 (lasers.out)
输出最少需要的镜子的数量。
2.4 输入样例
4 0 0 7 2
3 2
0 2
1 6
3 0
2.5 输出样例
1
2 激光和镜子 (LASERS.CPP/C/PAS) 5
2.6 样例解释
沿竖直方向发出一束光，在 (0,2) 处放置/的镜子，即可重定向到牛棚。
2.7 数据范围
测试点 N 坐标范围
1 ≤ 5
0 . . . 100
2 ≤ 10
3 ≤ 50
0 . . . 200
4 ≤ 100
5 ≤ 200
6 ≤ 500
7 ≤ 1, 000
0 . . . 2, 000
8 ≤ 2, 000
9 ≤ 5, 000
10
≤ 10, 000
11 0 . . . 1, 000, 000, 000
12
≤ 20, 000
0 . . . 2, 000
13 0 . . . 100, 000
14 0 . . . 1, 000, 000, 000
15
≤ 50, 000
0 . . . 100, 000
16 0 . . . 1, 000, 000, 000
17
≤ 100, 000
0 . . . 100, 000
18 0 . . . 1, 000, 000, 000
19
≤ 300, 000
0 . . . 150, 000
20 0 . . . 1, 000, 000, 000
3 干草堆猜测 (BALES.CPP/C/PAS) 6
3 干草堆猜测 (bales.cpp/c/pas)
3.1 题目描述
奶牛们设计了一个猜数游戏，来锻炼它们的逻辑推理能力。
游戏开始前，一头奶牛会在牛棚后面摆 N 堆干草 (1 ≤ N ≤ 1, 000, 000)；每堆干
草有若干捆，数量在 1 . . . 1, 000, 000, 000 之间，并且没有两堆中的草一样多。所有干草
堆排成一条直线，从左到右编号 1 . . . N 。游戏开始后，参与游戏的奶牛会问 Q 个问题
(1 ≤ Q ≤ 300, 000)：编号为 Q
l
. . . Q
r
的草堆中 (1 ≤ Q
l
≤ Q
r
≤ N )，最小的那堆里有多
少捆草？
对于每个问题，摆干草的奶牛都要给出回答 A。奶牛们当然会做这个 RMQ 问题
了，但是现在，它们不知道每堆干草的数量。请你计算摆干草的奶牛第一个 自相矛盾
的回答。
3.2 输入格式 (bales.in)
第一行两个整数 N, Q。
接下来 Q 行，每行三个整数 Q
l
, Q
r
, A，描述了一个问题以及其回答。
3.3 输出格式 (bales.out)
如果摆干草的奶牛有可能完全正确地回答了所有问题，也就是说，能找到一种使得
所有回答都合理的摆放干草的方法，输出 0。否则输出一个 1 . . . Q 之间的数，表示第
一个自相矛盾的回答的编号。
3.4 输入样例
20 4
1 10 7
5 19 7
3 12 8
11 15 12
3.5 输出样例
3
3 干草堆猜测 (BALES.CPP/C/PAS) 7
3.6 样例解释
第三个问题的回答与前两个回答矛盾。因为每堆中的草的数量唯一，从前两个回答
中我们能推断出，编号 5 . . . 10 的干草堆中最小的那堆有 7 捆干草。很显然，第三个问
题的回答与这个推断矛盾。
3.7 数据范围
测试点 N Q A 性质
1 ≤ 5
≤ 10
≤ 5
=1
2 ≤ 20 ≤ 20
3 ≤ 100 ≤ 500 =2
4 ≤ 10
≤ 20
≤ 10 =1
5 ≤ 10, 000 ≤ 50, 000 =2
6 ≤ 1, 000 ≤ 50 ≤ 5, 000 =1
7 ≤ 100, 000 ≤ 100 ≤ 500, 000 =2
8 ≤ 10, 000 ≤ 200 ≤ 50, 000 =1
9 ≤ 1, 000, 000 ≤ 500 ≤ 5, 000, 000
=2
10
≤ 100, 000
≤ 1, 000 ≤ 500, 000
11 ≤ 2, 000
≤ 1, 000, 000, 000
=1
12 ≤ 5, 000 =2
13
≤ 20, 000
≤ 100, 000
=114 ≤ 500, 000 ≤ 500, 000
15 ≤ 100, 000 ≤ 50, 000
≤ 1, 000, 000, 000
16
≤ 1, 000, 000 ≤ 100, 000
=2
17 =3
18 ≤ 300, 000
≤ 300, 000 =119
≤ 1, 000, 000
20
性质
1. 无特殊性质
2. 所有的 A 互不相同
3. 所有的 A 相同
