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

全国信息学奥林匹克联赛（NOIP2009）复赛 普及组 第 1 页 共 6 页 全国信息学奥林匹克联赛（NOIP2009）复赛 普及组 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 多项式输出 分数线划定 细胞分裂 道路游戏 英文题目名称 poly score cell game 可执行文件名 poly score cell game 输入文件名 poly.in score.in cell.in game.in 输出文件名 poly.out score.out cell.out game.out 每个测试点时限 1秒 1秒 1秒 1秒 测试点数目 10 10 10 20 每个测试点分值 10 10 10 5 附加样例文件 有 有 有 有 结果比较方式 全文比较 过滤行末空格 及文末回车 全文比较 过滤行末空格及 文末回车 全文比较 过滤行末空格 及文末回车 全文比较 过滤行末空格 及文末回车 题目类型 传统 传统 传统 传统 二．提交源程序文件名 对于pascal语言 poly.pas score.pas cell.pas game.pas 对于C语言 poly.c score.c cell.c game.c 对于C++语言 poly.cpp score.cpp cell.cpp game.cpp 三．编译命令（不包含任何优化开关） 对于pascal语言 fpc poly.pas fpc score.pas fpc cell.pas fpc game.pas 对于C语言 gcc -o poly poly.c -lm gcc -o score score.c -lm gcc -o cell cell.c -lm gcc -o game game.c -lm 对于C++语言 g++ -o poly poly.cpp -lm g++ -o score score.cpp -lm g++ -o cell cell.cpp -lm g++ -o game game.cpp -lm 四．运行内存限制 内存上限 128M 128M 128M 128M 注意事项： 1、文件名（程序名和输入输出文件名）必须使用小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU 1.9GHz，内 存1G，上述时限以此配置为准。各 省在自测时可根据具体配置调整时限。 全国信息学奥林匹克联赛（NOIP2009）复赛 普及组 第 2 页 共 6 页 1．多项式输出 (poly.pas/c/cpp) 【问题描述】 一元n次多项式可用如下的表达式表示： 0 1 1 1 ... ) (a x a x a x a x f n n n n + + + + = − − ， 0 ≠ na 其中， i ix a 称为i次项， ia 称为i次项的系数。给出一个一元多项式各项的次数和系 数，请按照如下规定的格式要求输出该多项式： 1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。 2. 多项式中只包含系数不为0的项。 3. 如果多项式n次项系数为正，则多项式开头不出现“+”号，如果多项式n次项系 数为负，则多项式以“-”号开头。 4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项 系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0次的项， 其系数的绝对值为1，则无需输出1）。如 果x的指数大于1，则接下来紧跟的指数部分的形 式为“x^b”，其 中b为x的指数；如果x的指数为1，则接下来紧跟的指数部分形式为“x”； 如果x的指数为0，则仅需输出系数即可。 5. 多项式中，多项式的开头、结尾不含多余的空格。 【输入】 输入文件名为poly.in，共有2行 第一行1个整数，n，表示一元多项式的次数。 第二行有n+1个整数，其中第i个整数表示第n-i+1次项的系数，每两个整数之间用空 格隔开。 【输出】 输出文件poly.out共1行，按题目所述格式输出多项式。 【输入输出样例1】 poly.in poly.out 5 100 -1 1 -3 0 10 100x^5-x^4+x^3-3x^2+10 【输入输出样例2】 poly.in poly.out 3 -50 0 0 1 -50x^3+1 【数据范围】 1 ≤n≤100，多项式各次项系数的绝对值均不超过100。 全国信息学奥林匹克联赛（NOIP2009）复赛 普及组 第 3 页 共 6 页 2．分数线划定 (score.pas/c/cpp) 【问题描述】 世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才，A市对 所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根 据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150% （向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有 选手。 现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成 绩。 【输入】 输入文件名为score.in。 第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其 中n表示报名参加笔试的选手总数，m表示计划录取的志愿者人数。输入数据保证m*150% 向下取整后小于等于n。 第二行到第n+1行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k （1000 ≤ k ≤ 9999）和该选手的笔试成绩s（1 ≤ s ≤ 100）。数据保证选手的报名号各 不相同。 【输出】 输出文件score.out。 第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为 进入面试的选手的实际人数。 从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表