《IOI2006中国国家队选拔赛第二试》由会员分享，可在线阅读，更多相关《IOI2006中国国家队选拔赛第二试（12页珍藏版）》请在金锄头文库上搜索。
1、IOI2006选拔 第二试 题目一览5月13日 OverviewIOI2006中国国家队选拔赛第二试题目名称方块填数生日礼物投篮游戏英文代号fillgiftshoottingg可执行文件件名fillgiftshoottingg输入文件名名fill.ingift.inshoottingg.inn输出文件名名fill.outtshoottingg.ouut每个测试点点时限1秒3秒1秒测试点数目目101010每个测试点点分值101010附加文件无gift_libb无题目类型传统交互传统竞赛时间：20006年55月133日上午午8:15-113:115第1页 共8页IOI2006选拔 第二试 方块填数
2、5月13日 fill方块填数fill【问题描述述】最近，一个个方块填填数的游游戏风靡靡全球：给定一个nn*m的方块块。n行从上上到下标标号为11到n，m列从左左到右标标号为11到m。如果果一个方方格所在在的行的的标号和和所在的的列的标标号都是是奇数，那那么该方方格就称称为奇方方格。游游戏的开开始所有有的奇方方格中都都填上了了数。你你需要在在其他的的方格里填数，如如果填完完数后，方方块满足足下面条条件，你你就赢得得了这个个游戏：1、 任意一个aa1*b1的子方方块中所所有数的的和大于于0；2、 任意一个aa2*b2的子方方块中所所有数的的和小于于0；其中，a11、b1、a2、b2都是在在游戏的的
3、开始给给定的。一个a*b的子方块是指行标号在i（1in-a+1）到i+a-1之间，列标号在j(1jm-b+1)到j+b-1之间的所有的方格的集合。小P很喜欢欢这种游游戏，他他希望你你帮助写一一个程序序给出一一种填数数的方案案，或者者告诉他他这样的的方案不不存在。【输入文件件】第一行为用用空格分分开的66个正整整数n,m,a1,b1,a2,b2，都在在1到1100之之间。从第2行起起到+11行，每每一行有有个整数数，第ii+1行的的第k(k=1,2,) 个数数表示在在游戏开开始时方方块的第第2i-1行行，2jj-1列的的方格所所填的整整数。这这些整数数都在-1000到1000之间间。【输出文件件
4、】如果填数方方案不存存在，输输出一行行“No”。如果填数方方案存在在，第一一行输出出“Yess”。接下来的nn行，每每一行有有用空格格分开的的m个整数数，描述述一个填填数方案案。输出出的每一一个整数数必须在在-1009到109之间。【输入样例例】3 3 22 2 3 331 11 1【输出样例例】Yes1 -1 1-4 5 -41 -1 11-11-45-41-11【样例说明明】 填填完数后后，任意意 2*2的方方块中的的数字之之和是11；3*33的方块块中的数字字之和是是-1。第 3 页 共 8 页IOI2006选拔 第二试 生日礼物5月13日 gift 生日礼物物gift【问题描述述】今天
5、是CCC姐姐的的生日，小小K给姐姐姐精心心准备了了一份生生日礼物物。不过过为了刁刁难一下下姐姐，他他不想把把礼物直直接送给给她，而而是让她她自己找找到这份份礼物。CC姐姐的的生日聚聚会上，小小K神秘秘兮兮地地搬出了了n只小宝宝箱，它它们的重重量各不不相同。小小K事先先公布了了一部分分宝箱之之间的轻轻重关系系，然后后告诉CCC姐姐姐生日礼礼物已经经装在了了次重的的宝箱里里，不过过具体是是哪个宝宝箱，让让她自己己去找。CCC姐姐姐手边仅仅有的称称量工具具就是一一架天平平，每次次可以比比较两只只宝箱的的重量。她她不仅想想找到那那只次重重的宝箱箱，而且且想用尽尽量少的的称量次次数找到到它，因因为小KK
6、告诉她她，如果果她的策策略能保保证在最最坏情况况下称量量次数最最少的话话，她还还会得到到意外的的惊喜！【输入文件件】第一行是一一个整数数n，表示示宝箱的的个数。第二行是一一个整数数m，表示示事先公公布的宝宝箱间的的轻重关关系数目目。接下来的mm行，每每行两个个整数xx和y（1 x, yn）表示示事先公公布了宝宝箱x要重于于宝箱yy。【约定】 2 n 20000000 2 m 20000000 事先公布的的关系没没有自相相矛盾【交互方法法】本题是一道道交互式式题目，你你的程序序只可以以访问输输入文件件gifft.iin以及及和测试试库进行行交互。输入文件格格式如前前所述。测试库提供供了若干干函数
7、，它它们的用用法和作作用如下下： init必必须先调调用，但但只能调调用一次次，用作作初始化化测试库库。 compaare(x, y)的的作用是是比较第第x只宝宝箱和第第y只宝宝箱的重重量，11 x, yn。若第第x只宝箱箱比第yy只宝箱箱重，返返回1，否否则返回回-1。 answeer(xx)的作作用是向向测试库库报告结结果，xx表示次次重的宝宝箱的编编号。当当这个函函数被调调用后，测测试库会会自动中中止你的的程序。【对使用PPasccal选选手的提提示】你的程序应应当使用用如下的的语句引引用测试试库。uses gifft_llib_p;测试库使用用的函数数原型为为：proceedurre
8、iinitt;functtionncommparre(xx, yy: llonggintt): lonnginnt;proceedurre aanswwer(x: lonnginnt);【对使用CC/C+选手手的提示示】你应当建立立一个工工程，把把文件ggiftt_liib_cc.o包含含进来，然然后在程程序头加加一行：#inclludee “gifft_llib_c.hh”测试库使用用的函数数原型为为：void iniit();int ccompparee(innt, intt);void ansswerr(innt);【你如何测测试自己己的程序序】 除了按照上上述格式式建立ggiftt.i
9、nn之外，请请另外建建立一个个名为“gifft.ddat”的文件件。该文文件包含含n个互不不相同整整数，绝绝对值不不超过22*1009，依次次表示每每只宝箱箱的重量量。 执行你的程程序，此此时测试试库会产产生输出出文件ggiftt.loog，该该文件中中包括了了你程序序和库交交互的记记录和最最后的结结果。 如果程序正正常结束束，giift.logg的最后后一行包包含一个个整数，为为你查询询的次数数。 如果程序非非法退出出，我们们不保证证gifft.llog中中的内容容有意义义。 正式测试时时，测试试库会自自行生成成宝箱的的重量，并并使得每每次回答答尽量对对你不利利。【样例】gift.in内内容
10、如下下313 2gift.datt内容如如下10 1 100一种可能得得满分的的调用方方案如下下：Pascaal选手手的调用用方法C/C+选手的的调用方方法说明init;init();初始化程序序compaare(3,11);compaare(3,11);返回1compaare(2,11);compaare(2,11);返回-1answeer(11);answeer(11);1确实是次次重的宝宝箱，共共称量22次注意，该例例子只是是对库函函数的使使用说明明，并没没有算法法上的意意义。【评分方法法】如果你的程程序有下下列情况况之一，该该测试点点0分： 自行终止； 非法调用库库函数； 让测试库异异
11、常退出出。否则，该测测试点的的得分按按如下公公式计算算：其中YouurAnnsweer为你你的程序序的称量量次数，BestAnswer是最佳策略下的称量次数。【提示】输入量相当当大，请请自行选选择高效效的文件件读入方方式。第 8 页 共 8 页IOI2006选拔 第二试 投篮游戏5月13日 shooting投篮游戏shoottingg【问题描述述】在大学里，体体育课有有很多门门，每个个人都可可以选自自己最喜喜欢的项项目。KKingg这学期期选的是是篮球，因因为篮球球课的老老师是一一个十分分有趣的的人。上课的第一一天，老老师宣布布了这门门课的评评分规则则：有n个篮球球(n m)，老师事先先在每个
12、个球上写写了一个个整数(不一定定相同，绝绝对值小小于1000000)。有有m个篮，每个篮篮板上有有一个计计分器，显显示一个个整数。一个学生开始考核前先将所有计分器显示值赋为1。每个学生考考核时要要进行n次投篮篮：选择择任意一一个篮球球投向任任意一个个篮。最最后他必必须将所所有球全全部投出出且每个个球恰好好投出一一次，要要求每个个篮至少少被投进进过一次次。如果学生将将一个写写有整数数x的篮球球投进了了某个计计分器显显示为yy的篮，则则该篮板板上的计计分器显显示值将将从y变成yx。一个学生的的原始得得分S定义为为m个计分分器的显显示值之之和，如如果S越大则则老师给给这个学学生的最最终打分分越高（事
13、事实上，老老师根据据名次按按照正态态分布给给分，但但此超出出本题了了讨论范范围）。King是是一个神神投手，他他保证能能将n个球全全都投进进。但是是Kinng的数数学十分分糟糕，他他不知道道该如何何安排投篮篮，才能能使得自自己的原原始得分分最大，你你能帮帮帮他吗？【输入文件件】输入有多组组数据，每每组数据据有两行行：第一行两两个整数数n,m。第二行nn个整数数，用一一个空格格分开，表表示老师师在n个篮球球上分别别写下的的整数。文件以00 0结结尾。一一个文件件中最多多只有110组数数据。【输出文件件】每组数据一一行，包包含一个个整数SSmaxx，表示示最大可可能的原原始得分分。提示：Smmax可可
