10.NOIP2012普及组复赛试题

全国信息学奥林匹克联赛（NOIP2012）复赛

普及组

CCF 全国信息学奥林匹克联赛（NOIP2012）复赛

普及组

（请选手务必仔细阅读本页内容）

一．题目概况

中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 质因数分解 寻宝 摆花 文化之旅 prime treasure flower culture prime treasure flower culture prime.in treasure.in flower.in culture.in prime.out treasure.out flower.out culture.out 1 秒 1 秒 1 秒 1 秒 10 10 10 10 10 10 10 10 有 有 有 有 全文比较（过滤行末空格及文末回车） 传统 传统 传统 传统 二．提交源程序文件名

对于 C++语言 对于 C 语言 对于 pascal 语言

prime.cpp prime.c prime.pas treasure.cpp treasure.c treasure.pas

flower.cpp flower.c flower.pas

culture.cpp culture.c culture.pas 三．编译命令（不包含任何优化开关）

对于 C++语言 g++ -o prime g++ -o treasure g++ -o flower prime.cpp -lm treasure.cpp -lm flower.cpp -lm 对于 C 语言 gcc -o prime gcc -o treasure gcc-o flower prime.c -lm treasure.c -lm flower.c -lm 对于 pascal 语言 fpc prime.pas fpc treasure.pas fpc flower.pas g++ -o culture culture.cpp -lm gcc -o culture culture.c -lm fpc culture.pas 四．运行内存限制

内存上限 128M 128M 128M 128M 注意事项：

1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。

3、全国统一评测时采用的机器配置为：CPU Intel Core2 Quad Q8200 2.33GHz，内存 2G，上 述时限以此配置为准。

4、特别提醒：评测在 NOI Linux 下进行。

第 1 页

共 6 页

全国信息学奥林匹克联赛（NOIP2012）复赛

普及组

1.质因数分解

(prime.cpp/c/pas)

【问题描述】

已知正整数 n 是两个不同的质数的乘积，试求出较大的那个质数。

【输入】

输入文件名为 prime.in。

输入只有一行，包含一个正整数 n。

【输出】

输出文件名为 prime.out。

输出只有一行，包含一个正整数 p，即较大的那个质数。

【输入输出样例】

prime.in prime.out 21

7 【数据范围】

对于 60%的数据，6 ≤ n ≤ 1000。 对于 100%的数据，6 ≤ n ≤ 2*109。

2．寻宝

(treasure.cpp/c/pas)

【问题描述】

传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏 宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：

藏宝楼共有 N+1 层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外， 藏宝楼另有 N 层，每层 M 个房间，这 M 个房间围成一圈并按逆时针方向依次编号为 0，…， M-1。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个 指示牌，指示牌上有一个数字 x，表示从这个房间开始按逆时针方向选择第 x 个有楼梯的房 间（假定该房间的编号为 k），从该房间上楼，上楼后到达上一层的 k 号房间。比如当前房 间的指示牌上写着 2，则按逆时针方向开始尝试，找到第 2 个有楼梯的房间，从该房间上楼。 如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。

寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示 牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。

请帮助小明算出这个打开宝箱的密钥。

【输入】

输入文件为 treasure.in。

第 2 页

共 6 页

全国信息学奥林匹克联赛（NOIP2012）复赛

普及组

第一行 2 个整数 N 和 M，之间用一个空格隔开。N 表示除了顶层外藏宝楼共 N 层楼， M 表示除顶层外每层楼有 M 个房间。

接下来 N*M 行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况， 其中第(i-1)*M+j 行表示第 i 层 j-1 号房间的情况（i=1, 2, …, N；j=1, 2, … ,M）。第一个整数 表示该房间是否有楼梯通往上一层（0 表示没有，1 表示有），第二个整数表示指示牌上的数 字。注意，从 j 号房间的楼梯爬到上一层到达的房间一定也是 j 号房间。

最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号 从 0 开始）。

【输出】

输出文件名为 treasure.out。

输出只有一行，一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对 20123 取模的结果即可。

【输入输出样例】

treasure.in treasure.out 2 3 1 2 0 3 1 4 0 1 1 5 1 2 1

5 【输入输出样例说明】 第一层：

0 号房间，有楼梯通往上层，指示牌上的数字是 2；

1 号房间，无楼梯通往上层，指示牌上的数字是 3； 2 号房间，有楼梯通往上层，指示牌上的数字是 4；

第二层：

0 号房间，无楼梯通往上层，指示牌上的数字是 1； 1 号房间，有楼梯通往上层，指示牌上的数字是 5； 2 号房间，有楼梯通往上层，指示牌上的数字是 2；

小明首先进入第一层（底层）的 1 号房间，记下指示牌上的数字为 3，然后从这个房间

开始，沿逆时针方向选择第 3 个有楼梯的房间 2 号房间进入，上楼后到达第二层的 2 号房间，

记下指示牌上的数字为 2，由于当前房间本身有楼梯通向上层，该房间作为第一个有楼梯的 房间。因此，此时沿逆时针方向选择第 2 个有楼梯的房间即为 1 号房间，进入后上楼梯到达

顶层。这时把上述记下的指示牌上的数字加起来，即 3+2=5，所以打开宝箱的密钥就是 5。

【数据范围】

对于 50%数据，有 0

对于 100%数据，有 0

第 3 页

共 6 页

全国信息学奥林匹克联赛（NOIP2012）复赛

普及组

3．摆花

(flower.cpp/c/pas)

【问题描述】

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调

查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花，

规定第 i 种花不能超过 a盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到

i

大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

【输入】

输入文件 flower.in，共 2 行。

第一行包含两个正整数 n 和 m，中间用一个空格隔开。

第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1、a2、……an。

【输出】

输出文件名为 flower.out。

输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出

方案数对 1000007 取模的结果。

【输入输出样例 1】

flower.in flower.out 2 4 3 2 2 【输入输出样例说明】 有 2 种摆花的方案，分别是(1，1，1，2)， (1，1，2，2)。括号里的 1 和 2 表示两种花， 比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。

【数据范围】

对于 20%数据，有 0

对于 100%数据，有 0

第 4 页

共 6 页