百度之星程序设计大赛初赛题目2题

taohui

5.座位调整 <br />百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，效率会大大提高。因此，百度决定进行一次员工座位的大调整。<br /><br />调整的方法如下：<br />1．首先将办公区按照各种零食的摆放分成N个不同的区域（例如：可乐区，饼干区，牛奶区等等）；<br />2．每个员工对不同的零食区域有不同的喜好程度（喜好程度是1~100的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）；<br />3．由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案使得总的喜好程度最大。<br /><br /><br />输入要求：<br />文件第一行包含两个整数N，M(N&gt;=1，M&lt;=300)。分别表示N个区域和M个员工；<br />第二行是N个整数构成的数列a，其中a表示第i个区域可以容纳的员工数(1&lt;=a&lt;=M，a[1]+a[2]+...+a[N]=M)；<br />紧接着是一个M*N的矩阵P，P(i,j)表示第i个员工对第j个区域的喜好程度。例：<br />3 3<br />1 1 1<br />100 50 25<br />100 50 25<br />100 50 25<br />样例：in.txt<br /><br /><br />输出要求：<br />对于每个测试数据，输出可以达到的最大的喜好程度。例：<br />175<br />样例：out.txt<br /><br /><br />数据解释：<br />此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为100+50+25=175<br /><br /><br />评分规则：<br />1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过10秒，否则该用例不得分；<br />2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；<br />3．该题目共有4个测试用例，每个测试用例为一个输入文件。各测试用例占该题目分数的比例分别为25%，25%，25%，25%；<br />4．该题目20分。<br /><br />6.剪刀石头布 <br />N个小孩正在和你玩一种剪刀石头布游戏（剪刀赢布，布赢石头，石头赢剪刀）。N个小孩中有一个是裁判，其余小孩分成三组（不排除某些组没有任何成员的可能性），但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩M次，每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情况，然而你不会得知小孩具体出的是剪刀、石头还是布。已知各组的小孩分别只会出一种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选择出一种手势，因此没有人会知道裁判到底会出什么。请你在M次剪刀石头布游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，请说明最早在第几次游戏结束后你就能够确定谁是裁判。<br /><br />输入要求：<br />输入文件包含多组测试数据，每组测试数据第一行为两个整数N和M(1&lt;=N&lt;=500，0&lt;M&lt;=2000)，分别为小孩的个数和剪刀石头布游戏进行的次数。接下来M行，每行两个整数且中间以一个符号隔开。两个整数分别为进行游戏的两个小孩各自的编号（为小于N的非负整数）。符号的可能值为“=”、“&gt;”和“&lt;”，分别表示和局、第一个小孩胜和第二个小孩胜三种情况。例：<br />3 3<br />0&lt;1<br />1&lt;2<br />2&lt;0<br />3 5<br />0&lt;1<br />0&gt;1<br />1&lt;2<br />1&gt;2<br />0&lt;2<br />4 4<br />0&lt;1<br />0&gt;1<br />2&lt;3<br />2&gt;3<br />1 0<br />样例：in.txt<br /><br /><br />输出要求：<br />1．每组测试数据输出一行，若能猜出谁是裁判，则输出裁判的编号，并输出在第几次游戏结束后就能够确定谁是裁判，小孩的编号和游戏次数以一个空格隔开；<br />2．如果无法确定谁是裁判，输出-2；如果发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输出-1。例：<br />-2<br />1 4<br />-1<br />0 0<br />样例：out.txt