IOI2006中国国家队选拔赛第一试

IOI2006选拔第一试题目一览5月11日Overview第1页共7页IOI2006中国国家队选拔赛第一试题目名称歌唱王国寻找盆地拼图英文代号singlandbasinjigsaw可执行文件名singlandbasinjigsaw输入文件名singland.injigsaw.in输出文件名singland.outjigsaw.out每个测试点时限3秒3秒1秒测试点数目101010每个测试点分值101010附加文件无basin_libjigsaw_c题目类型传统交互传统竞赛时间：2006年5月11日上午8:15-13:15IOI2006选拔第一试歌唱王国5月11日singland第2页共7页歌唱王国singland【问题描述】在歌唱王国，所有人的名字都是一个非空的仅包含整数1~n的字符串。王国里生活着一大群咕噜兵，他们靠不停的歌唱首领——牛人酋长们的名字来获取力量。咕噜兵每一次歌唱过程是这样的：首先，他从整数生成器那儿获得一个数字，然后花一个时间单位将此数字唱出来，如果他发现某个牛人酋长的名字已经被歌唱出来（即此名字是歌唱序列的一个连续子串），那么这次歌唱过程就立即结束。相关名词定义歌唱序列：如果某人歌唱了x个数字，第i次歌唱的数字为ai，那么歌唱序列=(a1,a2,…,ax)。整数生成器：歌唱王国的神物，它有一个按钮，如果你按一下按钮，将从1~n数字中等概率的随机返回一个整数。歌唱时间：在一次歌唱过程中花费的时间。歌唱时间是随机的，无法预料；不过歌唱时间的期望值是固定的，此期望值即平均来说歌唱时间有多长，亦可称作平均歌唱时间。王国里的人非常喜欢歌唱，他们希望歌唱的时间越长越好，所以他们决定罢免一些牛人酋长，使得平均歌唱时间变长。但是他们不能罢免掉所有的牛人酋长，否则他们每次歌唱都无法停止，无法获取力量；于是他们决定只保留一个牛人酋长而罢免其余的牛人酋长。你的任务是：对于给定的n、牛人酋长的个数t以及每一个牛人酋长的名字，告诉王国里的人们，对于1≤i≤t，如果保留第i个牛人酋长，罢免掉其余的，那么平均歌唱时间将是多少。提示：此数为一个非负整数！输出要求：由于这个数字太大，所以你只需输出这个数的末4位数字。如果不足4位，则前面补0(见样例)。【输入文件】第一行，两个整数n、t；以下t行描述t个牛人酋长名字。文件第i+1(1≤i≤t)行格式如下第一个数为mi表示第i个牛人酋长的名字的长度，在一个空格之后，接下来有mi个数，用来描述这个牛人酋长的名字，相邻两个整数之间用一个空格分开。【输出文件】共t行，第i行为一个整数，表示若保留第i个牛人酋长而罢免其余的，则平IOI2006选拔第一试歌唱王国5月11日singland第3页共7页均歌唱时间最长的末四位数字是多少。【约定】1≤n≤105，t≤50，1≤mi≤105。有30%的数据满足n≤103，mi≤103有50%的数据满足n≤104，mi≤104【样例】样例1：输入：22113121输出：00020010解释：保留第1个牛人酋长罢免其余酋长时，一次歌唱结束时可能的歌唱序列为：1,2,1,2,2,1,2,2,2,1,……，它们的概率分别为1/2,1/4,1/8,1/16,……，歌唱时间为1,2,3,4,……。不难证明122iii≥=∑。保留第2个牛人酋长罢免其余酋长时，平均歌唱时间为10。样例2：输入：2616123123输出：3352解释：平均歌唱时间为308933352。IOI2006选拔第一试寻找盆地5月11日basin第4页共7页寻找盆地basin【问题描述】五一节到了，为了摆脱紧张且繁忙的学习生活，寻找久违的刺激，小强打算和朋友们去冒险城探险。冒险城是一个边长为n的正方形区域，被人为地划分成了n*n块小区域，每块小区域都是一个单位正方形。为了方便起见，我们定义第i行第j列的小区域坐标为(i,j)。我们称两块小区域(x1,y1)和(x2,y2)相邻，当且仅当它们有一条公共边，即|x1–y1|+|x2–y2|=1。每块小区域都有一个海拔高度（用实数表示），不同的小区域高度不同。小强想在这n*n块小区域中找到一块盆地，即一块比相邻小区域海拔都低的小区域。冒险城被一圈很高的围墙包围，所以盆地可以出现在边上，此时它只需比相邻的三块小区域海拔低；盆地甚至可以出现在角上，此时它只需比相邻的两块小区域海拔低。冒险城入口处有一个地形查询系统，每次查询可以输入两块不同的小区域，系统会告诉你谁的海拔高。由于查询速度很慢，小强想用尽量少的询问次数找到一块盆地，你能帮他设计一种方案吗？【交互方法】本题是一道交互式题目，你的程序应当和测试库进行交互，而不得访问任何文件（包括临时文件）。测试库提供了若干函数，它们的用法和作用如下：¾init必须先调用，但只能调用一次，用作初始化测试库。¾get_n的作用是返回冒险城的边长n。¾query(x1,y1,x2,y2)的作用是询问小区域(x1,y1)和(x2,y2)的相对高低。如果(x1,y1)比(x2,y2)高，则返回1，否则返回-1。¾answer(x,y)的作用是向测试库报告结果，(x,y)表示你找到的盆地的坐标。当这个函数被调用后，测试库会自动中止你的程序。【对使用Pascal选手的提示】你的程序应当使用如下的语句引用测试库。usesbasin_lib_p;测试库使用的函数原型为：procedureinit;functionget_n:longint;functionquery(x1,y1,x2,y2:longint):longint;procedureanswer(x,y:longint);【对使用C/C++选手的提示】你应当建立一个工程，把文件basin_lib_c.o包含进来，然后在程序头加一行：#include“basin_lib_c.h”测试库使用的函数原型为：voidinit();IOI2006选拔第一试寻找盆地5月11日basin第5页共7页intget_n();intquery(int,int,int,int);voidanswer(int,int);【你如何测试自己的程序】¾在工作目录下建立一个文件叫做basin.in，文件的第一行包括一个整数n为冒险城的边长。接下来的n行，每行n个实数，表示每个小区域的海拔高度。¾执行你的程序，此时测试库会产生输出文件basin.log，该文件中包括了你程序和库交互的记录和最后的结果。¾如果程序正常结束，basin.log的最后一行包含一个整数，为你查询的次数。¾如果程序非法退出，则我们不保证basin.log中的内容有意义。¾正式测试时，测试库会自行生成地形，并使得每次回答尽量对你不利。【约定】¾2≤n≤63【样例】basin.in内容如下一种可能得满分的调用方案如下：Pascal选手的调用方法C/C++选手的调用方法说明init;init();初始化程序query(3,3,2,3);query(3,3,2,3);返回1query(3,3,3,2);query(3,3,3,2);返回-1query(2,3,2,2);query(2,3,2,2);返回1query(1,3,2,3);query(1,3,2,3);返回1query(1,2,2,2);query(1,2,2,2);返回-1query(2,1,2,2);query(2,1,2,2);返回1query(1,2,1,1);query(1,2,1,1);返回-1query(1,3,1,2);query(1,3,1,2);返回1answer(1,2);answer(1,2);(1,2)确实是盆地，共查询8次注意，该例子只是对库函数的使用说明，并没有算法上的意义。【评分方法】如果你的程序有下列情况之一，该测试点0分：¾访问了任何文件(包括临时文件)或者自行终止；¾非法调用库函数；¾让测试库异常退出。¾查询次数超过200次。否则，该测试点满分。39.11.27.35.42.53.66.78.84.9IOI2006选拔第一试拼图5月11日jigsaw第6页共7页拼图jigsaw【问题描述】5岁的小P对剪纸很感兴趣，他总是喜欢把一个矩形的纸片剪成一个又一个的凸多边形。但是，每一次剪完后，他总是怀疑自己弄丢了一些纸片。聪明的他想到了一个方法来检测纸片是否弄丢：他将这些凸多边形拼起来，如果能够拼成一个矩形，他就认为纸片没有弄丢。由于纸片的数量不是很多，这个工作并不难。但是，久而久之，他对这项工作不感兴趣了，所以，他找到了你，希望你能够告诉他，这些凸多边形纸片能不能够拼成矩形。【输入文件】第一行只有一个正整数n（1≤n≤8），表示凸多边形的个数。以下n行每一行描述一个凸多边形，格式如下：第i+1行的第一个数mi（3≤mi≤8）表示凸多边形的点数，接下来有mi对实数，一对实数给出了一个点的坐标，这mi个顶点按照从任意一个顶点出发的逆时针顺序给出。且所有实数都在(-1000,1000)的范围内，小数点后不超过8位。【输出文件】如果不能拼成矩形，输出只有一行“No”。如果能拼成矩形，输出的第一行为“Yes”。接下来的n行描述拼法。如果能够拼成一个X*Y的矩形，那么矩形的四个顶点的坐标是(0,0)、(0,Y)、(X,Y)、(X,0)。这n行输出每一个凸多边形的顶点的坐标（拼成矩形后）。按照输入的顺序，即第一个输出的凸多边形对应输入的第一个凸多边形。对于每一个凸多边形，输出也按照输入的顺序，即一个多边形的第一个顶点对应输入的第一个顶点。这样，输出总共有n行，第i行有mi对数。【输入样例】34004-154044005-183034000-83-440【输出样例】Yes044358085843808800804304【样例说明】IOI2006选拔第一试拼图5月11日jigsaw第7页共7页如下图，左上、右上和左下描述了输入的凸多边形，右下描述了输出的的矩形。【注意】由于矩形纸片的两面的颜色不同，所以纸片只能旋转和平移，不能翻转。所以，输出的mi个顶点也应该是逆时针顺序的。【评分说明】两个实数之差的绝对值小于10-7时认为两个实数相等。【你如何测试自己的程序】¾在工作目录下建立输入文件jigsaw.in，写入你自己设计的输入数据。¾执行你的程序，产生输出文件jigsaw.out。¾执行检查程序./jigsaw_c该程序检查jigsaw.out中的方案是否合法，并把检查结果打印到屏幕。