2018年海淀区青少年程序设计思维挑战活动提高组试题

2018 年海淀区青少年程序设计思维挑战活动

提高组试题（每题100 分，共300 分)

答题要求：

（1）答题统一在windows 系统下使用DEVC++5.11 版本编程环境；

（2）在计算机D 盘根目录下创建一个以自己考号为文件名的文件夹。

如：D:\TG-506

（3）各题最后写好的源文件，按照题目规定的文件名存入上述文件夹中。

如：D:\TG-506（注意是每个人自己的考号）

transport.cpp

puzzle.cpp

field.cpp

（4）各题的输入输出文件名与源文件名仅仅是扩展名不同。

源文件的扩展名为“.cpp”，（每道题仅仅提交源文件）

输入文件的扩展名为“.in”，

输出文件的扩展名为“.out”。

（5）答案提交：

完成作答后，提交自己创建的整个文件夹，该文件夹仅仅包含各题的源文件，不能包含子文件夹，或其它任何文件。

（6）最终测试时：

所有编译命令均打开-O2优化开关。

transport 时限1s 空间限制：128M

puzzle 时限2s 空间限制：128M

field 时限1s 空间限制：128M

切记：答案严格按照题目要求命名。有疑问及时举手询问监考老师。

1.奥运场馆服务(transport.cpp)

【问题描述】

冬奥会在紧张的筹备过程当中，根据计划某个比赛日共有2*n 条线路需要提供观众的转场服务，上午和下午各n 条线路，安排n 个司机为当天的观众进行服务，使得上、下午的每条线路都恰好分配到一个司机。

组委会需要按照司机的行驶距离付费，在距离不超过r 时只需要支付基本费用，当距离超过r，按照每单位距离s 元付费。

【输入格式】

输入文件包含多组测试数据。每组数据的第一行包含3 个整数n，r，s；第二行包含n 个整数，即上午各条线路的的行驶距离；第三行包含n 个整数，即下午各条线路的形式距离。行驶距离不超均为不超过10 000 的正整数。当n，r，s 都为0 时输入结束。

【输出格式】

对于每组数据，输出支付给每个司机基本费用之外的最小费用。

【样例输入】

2 100 5

50 50 50

50

2 100 5

50 60 50

60 0 0 0

【样例输出】

100

【数据规模与约定】

对于100%的数据，1 ≤ n ≤ 1000，1 ≤ r ≤ 10000，1 ≤ s ≤ 200。

第2页共5页

2.拼图游戏(puzzle.cpp)

【问题描述】

九宫格拼图大家都很熟悉，在3x3的格子上摆放8块拼图，空出一个格子，玩家要借助这1个空格上下左右滑动拼图，最终完成整幅图画。

本题中对拼图进行简化，将正确位置的拼图从左到右自上而下标记为1-8，空格定义为0，像下面这样：

1 3 0

4 2 5

7 8 6

每次操作可以将1块拼图移向空格，像下面这样将8块拼图全部归位时完成游戏。

1 2 3

4 5 6

7 8 0

现在给定拼图的初始状态，希望求出完成拼图最少需要多少次移动。

【输入格式】

输入文件第一行有一个数字N，表示测试样例组数；

以下3*N行共包含N组测试数据，每组测试数据占3行，每行3个整数，相邻数据用空格隔开。

【输出格式】

输出文件包括N行，对于每组测试数据，输出最少移动次数。

【样例输入】

1

1 3 0

4 2 5

7 8 6

【样例输出】

4

【样例说明】

1 3 0 1 0 3 1

2

3 1 2 3 1 2 3

4 2

5 4 2 5 4 0 5 4 5 0 4 5 6

7 8 6 7 8 6 7 8 6 7 8 6 7 8 0 【数据规模与约定】

1 ≤ N ≤ 30，保证给定的拼图有解。

3.有限域(field.cpp)

【问题描述】

在抽象代数中，有一个关于有限域的定理：存在一个大小为q 的有限域当且仅当q 是某个素数p 的方幂，即q=p^k，k>=1，且在同构意义下，相同大小的有限域只有一个。

你决定运用这个定理写一个程序来计算同构意义下的不同有限域个数。对于一个给定的输入n，你需要计算有多少个不同构的有限域，他们的大小是不超过n 的。

【输入格式】

输入文件包含多组测试数据，每组测试数据包含一个正整数n。

【输出格式】

输出文件包含多行，对于每行输入，输出阶数（即大小）不超过n 的有限域的个数。

【样例输入】

2

37

【样例输出】

1

19

【样例说明】

不大于2的有限域包括：2

不大于37的有限域包括：2 3 4 5 7 8 9 11 13 16 17 19 23 25

27 29 31 32 37

【数据规模与约定】

对于30%的数据，1 ≤ n ≤ 100

对于100%的数据，1 ≤ n ≤ 40000