人力资源-IOI2006中国国家队选拔赛第二试VIP专享VIP免费

IOI2006中国国家队选拔赛第二试题目名称方块填数生日礼物投篮游戏英文代号fillgiftshooting可执行文件名fillgiftshooting输入文件名fill.ingift.inshooting.in输出文件名fill.outshooting.out每个测试点时限1秒3秒1秒测试点数目101010每个测试点分值101010附加文件无gift_lib无题目类型传统交互传统竞赛时间：2006年5月13日上午8:15-13:15方块填数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行起到+1行，每一行有个整数，第i+1行的第k(k=1,2,…,)个数表示在游戏开始时方块的第2i-1行，2j-1列的方格所填的整数。这些整数都在-100到100之间。【输出文件】如果填数方案不存在，输出一行“No”。如果填数方案存在，第一行输出“Yes”。接下来的n行，每一行有用空格分开的m个整数，描述一个填数方案。输出的每一个整数必须在-109到109之间。【输入样例】3322331111【输出样例】Yes1-11-45-41-11-45-41-111-11【样例说明】填完数后，任意2*2的方块中的数字之和是1；3*3的方块中的数字之和是-1。生日礼物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);3132101100【对使用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，该文件中包括了你程序和库交...