2012年信息学奥赛NOIP普及组复赛C++真题

全国信息学奥林匹克联赛（ NOIP201 2）复赛 普及组 第 1页 共 6页 CCF 全国信息学奥林匹克联赛 （ NOIP20 12） 复赛 普及 组 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 质因数分解 寻宝 摆花 文化之旅 英文题目与子目录名 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++ 语言 prime .cpp treasure .cpp flower .cpp culture .cpp 对于 C语言 prime .c treasure .c flower .c culture .c 对于 pascal 语言 prime .pas treasure .pas flower .pas culture .pas 三．编译命令（不包含任何优化开关） 对于 C++ 语言 g++ -o prime prime .cpp -lm g++ -o treasure treasure .cpp -lm g++ -o flower flower .cpp -lm g++ -o culture culture .cpp -lm 对于 C语言 gcc -o prime prime .c -lm gcc -o treasure treasure .c -lm gcc -o flower flower .c -lm gcc -o culture culture .c -lm 对于 pascal 语言 fpc prime .pas fpc treasure .pas fpc flower .pas 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 下进行。 全国信息学奥林匹克联赛（ NOIP201 2）复赛 普及组 第 2页 共 6页 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*10 9。 2． 寻宝 (treasure .cpp/c/pas ) 【问题描述】 传说很遥远的藏宝楼顶层藏着 诱人 的宝藏。 小明 历尽千辛万苦终于找到传说中的这个藏 宝楼，藏宝楼的门口 竖着 一个木板， 上面写有 几个大字 ： 寻宝说明书。说明书的内容如下： 藏宝楼 共有 N+1 层 ，最上面一层是顶层 ，顶层 有一个房间 里面 藏着宝藏。 除 了 顶层外 ， 藏 宝 楼另有 N 层， 每层 M 个房间 ，这 M 个房间围成一圈并按逆时针方向依次编号为 0，…， M-1。其中一 些房间有通往上 一层的楼梯，每层楼的楼梯 设计 可能 不 同 。每个 房间里有一个 指示牌，指示牌上有一个数字 x，表示 从 这个房间 开始 按逆时针方向 选择第 x个有楼梯的房 间 （假定该房间的编号为 k）， 从该房间上楼 ，上楼后到达上一层的 k号房间 。 比如当前房 间的指示牌上写着 2，则 按 逆时针方向 开始尝试，找到第 2个有楼梯的房间，从该房间上楼。 如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。 寻宝说明书的最后用红色大号字体写着 ：“ 寻宝须知 ： 帮助你找到每层上楼房间的指示 牌上的数字 （即每层第一个进入的房间内指示牌上 的 数字）总和 为打开宝箱的密钥 ”。 请 帮助小明算出这个打开宝箱的密钥 。 【输入】 输入文件 为 treasure .in 。 全国信息学奥林匹克联赛（ NOIP201 2）复赛 普及组 第 3页 共 6页 第一行 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号房间。 最后一行，一个整数， 表示小明 从