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

IOI2006选拔第二试题目一览5月13日Overview第1页共8页IOI2006中国国家队选拔赛第二试题目名称方块填数生日礼物投篮游戏英文代号fillgiftshooting可执行文件名fillgiftshooting输入文件名fill.ingift.inshooting.in输出文件名fill.outshooting.out每个测试点时限1秒3秒1秒测试点数目101010每个测试点分值101010附加文件无gift_lib无题目类型传统交互传统竞赛时间：2006年5月13日上午8:15-13:15IOI2006选拔第二试方块填数5月13日fill第2页共8页方块填数fill【问题描述】最近，一个方块填数的游戏风靡全球：给定一个n*m的方块。n行从上到下标号为1到n，m列从左到右标号为1到m。如果一个方格所在的行的标号和所在的列的标号都是奇数，那么该方格就称为奇方格。游戏的开始所有的奇方格中都填上了数。你需要在其他的方格里填数，如果填完数后，方块满足下面条件，你就赢得了这个游戏：1、任意一个a1*b1的子方块中所有数的和大于0；2、任意一个a2*b2的子方块中所有数的和小于0；其中，a1、b1、a2、b2都是在游戏的开始给定的。一个a*b的子方块是指行标号在i（1≤i≤n-a+1）到i+a-1之间，列标号在j(1≤j≤m-b+1)到j+b-1之间的所有的方格的集合。小P很喜欢这种游戏，他希望你帮助写一个程序给出一种填数的方案，或者告诉他这样的方案不存在。【输入文件】第一行为用空格分开的6个正整数n,m,a1,b1,a2,b2，都在1到100之间。从第2行起到12n+1行，每一行有12m个整数，第i+1行的第k(k=1,2,…,12m)个数表示在游戏开始时方块的第2i-1行，2j-1列的方格所填的整数。这些整数都在-100到100之间。【输出文件】如果填数方案不存在，输出一行“No”。如果填数方案存在，第一行输出“Yes”。接下来的n行，每一行有用空格分开的m个整数，描述一个填数方案。输出的每一个整数必须在-109到109之间。【输入样例】3322331111【输出样例】Yes1-11-45-4IOI2006选拔第二试方块填数5月13日fill第3页共8页1-11【样例说明】填完数后，任意2*2的方块中的数字之和是1；3*3的方块中的数字之和是-1。1-11-45-41-11IOI2006选拔第二试生日礼物5月13日gift第4页共8页生日礼物gift【问题描述】今天是CC姐姐的生日，小K给姐姐精心准备了一份生日礼物。不过为了刁难一下姐姐，他不想把礼物直接送给她，而是让她自己找到这份礼物。CC姐姐的生日聚会上，小K神秘兮兮地搬出了n只小宝箱，它们的重量各不相同。小K事先公布了一部分宝箱之间的轻重关系，然后告诉CC姐姐生日礼物已经装在了次重的宝箱里，不过具体是哪个宝箱，让她自己去找。CC姐姐手边仅有的称量工具就是一架天平，每次可以比较两只宝箱的重量。她不仅想找到那只次重的宝箱，而且想用尽量少的称量次数找到它，因为小K告诉她，如果她的策略能保证在最坏情况下称量次数最少的话，她还会得到意外的惊喜！【输入文件】第一行是一个整数n，表示宝箱的个数。第二行是一个整数m，表示事先公布的宝箱间的轻重关系数目。接下来的m行，每行两个整数x和y（1≤x,y≤n）表示事先公布了宝箱x要重于宝箱y。【约定】2≤n≤2000002≤m≤200000事先公布的关系没有自相矛盾【交互方法】本题是一道交互式题目，你的程序只可以访问输入文件gift.in以及和测试库进行交互。输入文件格式如前所述。测试库提供了若干函数，它们的用法和作用如下：init必须先调用，但只能调用一次，用作初始化测试库。compare(x,y)的作用是比较第x只宝箱和第y只宝箱的重量，1≤x,y≤n。若第x只宝箱比第y只宝箱重，返回1，否则返回-1。answer(x)的作用是向测试库报告结果，x表示次重的宝箱的编号。当这个函数被调用后，测试库会自动中止你的程序。【对使用Pascal选手的提示】你的程序应当使用如下的语句引用测试库。usesgift_lib_p;测试库使用的函数原型为：procedureinit;functioncompare(x,y:longint):longint;procedureanswer(x:longint);IOI2006选拔第二试生日礼物5月13日gift第5页共8页【对使用C/C++选手的提示】你应当建立一个工程，把文件gift_lib_c.o包含进来，然后在程序头加一行：#include“gift_lib_c.h”测试库使用的函数原型为：voidinit();intcompare(int,int);voidanswer(int);【你如何测试自己的程序】除了按照上述格式建立gift.in之外，请另外建立一个名为“gift.dat”的文件。该文件包含n个互不相同整数，绝对值不超过2*109，依次表示每只宝箱的重量。执行你的程序，此时测试库会产生输出文件gift.log，该文件中包括了你程序和库交互的记录和最后的结果。如果程序正常结束，gift.log的最后一行包含一个整数，为你查询的次数。如果程序非法退出，我们不保证gift.log中的内容有意义。正式测试时，测试库会自行生成宝箱的重量，并使得每次回答尽量对你不利。【样例】gift.in内容如下gift.dat内容如下一种可能得满分的调用方案如下：Pascal选手的调用方法C/C++选手的调用方法说明init;init();初始化程序compare(3,1);compare(3,1);返回1compare(2,1);compare(2,1);返回-1answer(1);answer(1);1确实是次重的宝箱，共称量2次注意，该例子只是对库函数的使用说明，并没有算法上的意义。【评分方法】如果你的程序有下列情况之一，该测试点0分：自行终止；非法调用库函数；让测试库异常退出。否则，该测试点的得分按如下公式计算：1011003132IOI2006选拔第二试生日礼物5月13日gift第6页共8页20log12427110YourAnswernnYourAnswerBestAnswerYourScoreYourAnswerBestAnswerYourAnswerBestAnswerYourAnswerBestAnswer其中YourAnswer为你的程序的称量次数，BestAnswer是最佳策略下的称量次数。【提示】输入量相当大，请自行选择高效的文件读入方式。IOI2006选拔第二试投篮游戏5月13日shooting第7页共8页投篮游戏shooting【问题描述】在大学里，体育课有很多门，每个人都可以选自己最喜欢的项目。King这学期选的是篮球，因为篮球课的老师是一个十分有趣的人。上课的第一天，老师宣布了这门课的评分规则：有n个篮球(n≥m)，老师事先在每个球上写了一个整数(不一定相同，绝对值小于10000)。有m个篮，每个篮板上有一个计分器，显示一个整数。一个学生开始考核前先将所有计分器显示值赋为1。每个学生考核时要进行n次投篮：选择任意一个篮球投向任意一个篮。最后他必须将所有球全部投出且每个球恰好投出一次，要求每个篮至少被投进过一次。如果学生将一个写有整数x的篮球投进了某个计分器显示为y的篮，则该篮板上的计分器显示值将从y变成y×x。一个学生的原始得分S定义为m个计分器的显示值之和，如果S越大则老师给这个学生的最终打分越高（事实上，老师根据名次按照正态分布给分，但此超出本题了讨论范围）。King是一个神投手，他保证能将n个球全都投进。但是King的数学十分糟糕，他不知道该如何安排投篮，才能使得自己的原始得分最大，你能帮帮他吗？【输入文件】输入有多组数据，每组数据有两行：第一行两个整数n,m。第二行n个整数，用一个空格分开，表示老师在n个篮球上分别写下的整数。文件以00结尾。一个文件中最多只有10组数据。【输出文件】每组数据一行，包含一个整数Smax，表示最大可能的原始得分。提示：Smax可能超过任何基本整数类型。Smax也可能比0小。【约定】1≤m≤n≤2000恰有40%的数据满足n≤100IOI2006选拔第二试投篮游戏5月13日shooting第8页共8页【输入样例】1020-1-2012321011030-1-20123210100【输出样例】240241【样例说明】第一组数据有多解，其中一解为：(0,0)(-1,-2,1,2,3,2,10,1)第二组数据有多解，其中一解为：(0,0)(1,1)(-1,-2,2,3,2,10)