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

全国信息学奥林匹克联赛（NOIP2010）复赛 普及组 第 1 页 共 7 页 全国信息学奥林匹克联赛（NOIP2010）复赛 普及组 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 数字统计 接水问题 导弹拦截 三国游戏 英文题目与子目录名 two water missile sanguo 可执行文件名 two water missile sanguo 输入文件名 two.in water.in missile.in sanguo.in 输出文件名 two.out water.out missile.out sanguo.out 每个测试点时限 1秒 1秒 1秒 1秒 测试点数目 10 10 10 10 每个测试点分值 10 10 10 10 附加样例文件 有 有 有 有 结果比较方式 全文比较（过滤行末空格及文末回车） 题目类型 传统 传统 传统 传统 二．提交源程序文件名 对于pascal语言 two.pas water. pas missile. pas sanguo. pas 对于C语言 two.c water.c missile.c sanguo.c 对于C++语言 two.cpp water.cpp missile.cpp sanguo.cpp 三．编译命令（不包含任何优化开关） 对于pascal语言 fpc two.pas fpc water.pas fpc missile.pas fpc sanguo.pas 对于C语言 gcc -o two two.c -lm gcc -o water water.c -lm gcc -o missile missile.c -lm gcc -o sanguo sanguo.c -lm 对于C++语言 g++ -o two two.cpp -lm g++ -o water water.cpp -lm g++ -o missile missile.cpp -lm g++ -o sanguo sanguo.cpp -lm 四．运行内存限制 内存上限 128M 128M 128M 128M 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU P4 3.0GHz，内 存1G，上述时限以此配置为准。 各省在自测时可根据具体配置调整时限。 全国信息学奥林匹克联赛（NOIP2010）复赛 普及组 第 2 页 共 7 页 1．数字统计 (two.pas/c/cpp) 【问题描述】 请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。 比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出 现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6 次。 【输入】 输入文件名为two.in。 输入共1行，为两个正整数L和R，之间用一个空格隔开。 【输出】 输出文件名为two.out。 输出共1行，表示数字2出现的次数。 【输入输出样例1】 two.in two.out 2 22 6 【输入输出样例2】 two.in two.out 2 100 20 【数据范围】 1 ≤L≤R≤10000。 2．接水问题 (water.pas/c/cpp) 【问题描述】 学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的 供水量相等，均为1。 现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1 到n编号，i号同学的接水量为w i。接水开始时，1到m号同学各占一个水龙头，并同时打 开水龙头接水。当其中某名同学j完成其接水量要求w j后，下一名排队等候接水的同学k 马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j同学第x秒结束时完成接水，则k同学第x+1秒立刻开始接水。若当前接水人数n’不足m， 则只有n’个龙头供水，其它m−n’个龙头关闭。 现在给出n名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。 全国信息学奥林匹克联赛（NOIP2010）复赛 普及组 第 3 页 共 7 页 【输入】 输入文件名为water.in。 第1行2个整数n和m，用一个空格隔开，分别表示接水人数和龙头个数。 第2行n个整数w 1、w 2、……、w n，每两个整数之间用一个空格隔开，w i表示i号同 学的接水量。 【输出】 输出文件名为water.out。 输出只有一行，1个整数，表示接水所需的总时间。 【输入输出样例1】 water.in water.out 5 3 4 4 1 2 1 4 【输入输出样例1说明】 第1秒，3人接水。第1秒结束时，1、2、3号同学每人的已接水量为1，3号同学接完 水，4号同学接替3号同学开始接水。 第2秒，3人接水。第2秒结束时，1、2号同学每人的已接水量为2，4号同学的已接 水量为1。 第3秒，3人接水。第3秒结束时，1、2号同学每人的已接水量为3，4号同学的已接 水量为2。4号同学接完水，5号同学接替4号同学开始接水。 第4秒，3人接水。第4秒结束时，1、2号同学每人的已接水量为4，5号同学的已接 水量为1。1、2、5号同学接完水，即所有人完成接水。 总接水时间为4秒。 【输入输出样例2】 water.in water.out 8 4 23 71 87 32 70 93 80 76 163 【数据范围】 1 ≤n≤10000，1 ≤m≤100且m ≤n； 1 ≤wi≤100。 3．导弹拦截 (missile.pas/c/cpp) 【问题描述】 经过11年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过 其工作半径的导弹都能够被它成功拦截。当工作半径为0时，则能够拦截与它位置恰好相同 的导弹。但该导弹拦截系统