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

全国信息学奥林匹克联赛（NOIP2014）复赛 普及组 第1页共6页 CCF全国信息学奥林匹克联赛（NOIP2014）复赛 普及组 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 珠心算测试 比例简化 螺旋矩阵 子矩阵 英文题目与子目录名 count ratio matrix submatrix 可执行文件名 count ratio matrix submatrix 输入文件名 count.in ratio.in matrix.in submatrix.in 输出文件名 count.out ratio.out matrix.out submatrix.out 每个测试点时限 1秒 1秒 1秒 1秒 测试点数目 10 10 10 20 每个测试点分值 10 10 10 5 附加样例文件 有 有 有 有 结果比较方式 全文比较（过滤行末空格及文末回车） 题目类型 传统 传统 传统 传统 运行内存上限 128M 128M 128M 128M 二．提交源程序文件名 对于C++语言 count.cpp ratio.cpp matrix.cpp submatrix.cpp 对于C语言 count.c ratio.c matrix.c submatrix.c 对于pascal语言 count.pas ratio.pas matrix.pas submatrix.pas 三．编译命令（不包含任何优化开关） 对于C++语言 g++ -o count count.cpp -lm g++ -o ratio ratio.cpp -lm g++ -o matrix matrix.cpp -lm g++ -o submatrix submatrix.cpp -lm 对于C语言 gcc -o count count.c -lm gcc -o ratio ratio.c -lm gcc -o matrix matrix.c -lm gcc -o submatrix submatrix.c -lm 对于pascal语言 fpc count.pas fpc ratio.pas fpc matrix.pas fpc submatrix.pas 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+，2.71GHz，内存2G，上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特 别 提 醒 ：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。 全国信息学奥林匹克联赛（NOIP2014）复赛 普及组 第2页共6页 1. 珠心算测验 (count.cpp/c/pas) 【问题描述】 珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？ 最近老师出了一些测验题，请你帮忙求出答案。 【输入】 输入文件名为count.in。 输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。 第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。 【输出】 输出文件名为count.out。 输出共一行，包含一个整数，表示测验题答案。 【输入输出样例】 count.in count.out 4 1 2 3 4 2 【样例说明】 由1+2=3，1+3=4，故满足测试要求的答案为2。注意，加数和被加数必须是集合中的两个不同的数。 【数据说明】 对于100%的数据，3 ≤ n ≤ 100，测验题给出的正整数大小不超过10,000。 全国信息学奥林匹克联赛（NOIP2014）复赛 普及组 第3页共6页 2.比例简化 （ratio.cpp/c/pas） 【问题描述】 在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有1498人，反对的有902人，那么赞同与反对的比例可以简单的记为1498:902。 不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。 现给出支持人数A，反对人数B，以及一个上限L，请你将A比B化简为A’比B’，要求在A’和B’均不大于L且A’和B’互质（两个整数的最大公约数是1）的 前 提 下 ，A’/B’ ≥ A/B且A’/B’ - A/B的值尽可能小。 【输入】 输入文件名为ratio.in。 输入共一行，包含三个整数A，B，L，每 两 个 整 数 之 间 用 一 个 空 格 隔 开 ，分 别 表 示 支 持人数、反对人数以及上限。 【输出】 输出文件名为ratio.out。 输出共一行，包含两个整数A’，B’，中间用一个空格隔开，表示化简后的比例。 【输入输出样例】 ratio.in ratio.out 1498 902 10 5 3 【数据说明】 对于100%的数据，1 ≤ A ≤ 1,000,000，1 ≤ B ≤ 1,000,000，1 ≤ L ≤ 100， A/B ≤ L。 全国信息学奥林匹克联赛（NOIP2014）复赛 普及组 第4页共6页 3. 螺旋矩阵 (matrix.cpp/c/pas) 【问题描述】 一个n行n列的螺旋矩阵可由如下方法生成： 从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1, 2, 3, ... , n2，便构成了一个螺旋矩阵。 下图是一个n = 4 时的螺旋矩阵。 1 2 3 4 12