2006百度之星程序设计大赛试题-变态比赛规则(解答)

 2006百度之星程序设计大赛试题-变态比赛规则(解答)
题目+源码打包下载
http://www.cppblog.com/Files/zuroc/kof_rule.zip

变态比赛规则

为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛，负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。

由于一些员工（比如同部门或者相邻部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自由分组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。

比如4个人，编号为1~4,如果分为两个组并且1，2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如

果是1，2，3一组，4单独一组，那么一共需要打三场比赛 1 vs 4，2 vs 4，3 vs 4。


很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人，通过上面这种比赛规则，总比赛场数有可能为K场吗？

比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛，如果分为三组则需要3场比赛。但是无论怎么分都不可能恰需要1场比赛。


相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。


输入要求：
每行为一组数据，包含两个数字 N, K(0N=500, K=0)。例：
2 0
2 1
3 1
3 2
样例：in.txt



输出要求：
对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K，则输出YES，否则输出NO（请全部使用大写字母），每组数据占一行。例：
YES
YES
NO
YES
样例：out.txt


评分规则：
1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试数据集上运行不能超过10秒，否则该用例不得分；
2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3．该题目共有3个测试数据集，每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为30%，30%，40%；
4．该题目20分。

10人的话：
最多可以多少场？
1，1，1，1，1，1，1，1，1，1
这样每个人都要与其它人踢。。。
10+9+8+7+6+5+4+3+2+1＝
2，1，1，1，1，1，1，1，1
这样只会少一场。。。就是第一队中的两个人不用互踢
10+9+8+7+6+5+4+3+2=
3,1,1,1,1,1,1,1
以上一次少二场。。。就是有同一队中三个人不用互踢（比上上次要少 2+1场）
10+9+8+7+6+5+4+3＝
3，2，1，1，1，1，1
比上一个少一场
3，3，1，1，1，1
比上一个少二场
。。。。。。。
总场数为：
Sn(总人数)-Sn(第一组人数)－Sn(第二组人数)－Sn(第三组人数)
＝N
等比数列
Sn(总人数)－N＝Sn(team1)+Sn(team2)....
假设
Sn(team1)<Sn(总数)－N<Sn(team1+1)
得出tean1=x
Sn(总人数－team1)-(N-Sn(team1))=Sn(team2)+Sn(team3)...

结束条件想不出来。。。

package com.maodajun.javaeye1;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class BaiDuQuest {

	public String teamAndImpossable(int peoples,int impossable){
		int maximpossable= maxImpossable(peoples);
		maximpossable -=impossable;
		List list =selfTeam(peoples,maximpossable,new ArrayList());
		if(list!=null){
			return "YES";
		}
		return "NO";	
	}
	//递归算出最大可能。。。循环赛制
	public int maxImpossable(int poples){
		
		if(poples==2){
			return 1;
		}else if(poples<1){
			return 0;
		}
		poples--;
		return maxImpossable(poples)+poples;
	}
	
	public int maxFirstTeam(int peoples, int maximpossable){
		int tmp = 0 ;
		if(maxImpossable(peoples)<maximpossable){
			return -1;
		}
		for(int i = peoples ; i >1 ; i--){
			tmp = maxImpossable(i);
			if(tmp <= maximpossable){
				return i;
			}
		}
		return tmp;
	}
	public List selfTeam(int peoples , int maximpossable ,List list ){
		int max = maxFirstTeam(peoples,maximpossable);
		if(max==0){
			return list;
		}else if (max==-1){
			return null;
		}else{
			list .add(""+max);
			return selfTeam(peoples-max,maximpossable-maxImpossable(max),list);
		}	
	}
	public static  void main(String[] arg){
		BaiDuQuest quest = new BaiDuQuest();
		int people = 5;
		for(int i = quest.maxImpossable(people) ; i >=0; i--){
			List list =quest.selfTeam(people,i,new ArrayList());
			int count = 0 ;
			if(list!=null){
				for(int j = 0 ; j < list.size(); j ++){
					 count +=Integer.parseInt(list.get(j).toString());
					
				}
	
				list.add(""+(people-count));
			}
			System.out.println(quest.maxImpossable(people)-i+":"+list);
		}
	}
	 
	

}

package com.maodajun.javaeye1;

import java.util.ArrayList;
import java.util.List;

import junit.framework.TestCase;

/**
 * @author maodajun327
 *
 */
public class BaiDuQuestTest extends TestCase {
	BaiDuQuest quest = null;
	public static void main(String[] args) {
		junit.textui.TestRunner.run(BaiDuQuestTest.class);
	}

	public void setUp(){
		quest =new BaiDuQuest();;
	}

	public void testMaxImpossable(){
		assertEquals(0,quest.maxImpossable(1));
		assertEquals(1,quest.maxImpossable(2));
		assertEquals(3,quest.maxImpossable(3));
		assertEquals(6,quest.maxImpossable(4));
		assertEquals(10,quest.maxImpossable(5));
	}
	public void testListMax(){
		assertEquals(1,quest.maxFirstTeam(4,0));//如果有6－1场赛时第一组1人
		assertEquals(2,quest.maxFirstTeam(4,2));//如果有6－3场赛时第一组2人
		assertEquals(3,quest.maxFirstTeam(4,3));//如果有6－4场赛时第一组3人
		assertEquals(4,quest.maxFirstTeam(4,6));//如果有6－6场赛时第一组为4人
		assertEquals(-1,quest.maxFirstTeam(4,7));//小于0场时第一组为－1人		
	}
	public void testSelfTeam(){

		List list =null;
		list = quest.selfTeam(5,6,new ArrayList());
		assertNotNull(list);
		list = quest.selfTeam(5,7,new ArrayList());
		assertNull(list);
	}
	public void testTeamAndImpossable(){

		 String tmp=null;
		 tmp = quest.teamAndImpossable(5,4);
		assertEquals("YES",tmp);
		tmp = quest.teamAndImpossable(5,5);
		assertEquals("NO",tmp);
	}

}

大致看了下题目，我的理解是：
输入N（人），场数为K。而按比赛规则，假设两组分别有为x、y人，那可以得出这样的结论：
x+y=N
x*y=K
换算和可以得到：
x*x-N*x+K=0
y*y-N*y+K=0
而从中可以看到，要使等式成立，只要
(y-N/2)*(y-N/2)=0 => y*y-N*y+N*N/4=0
即N*N/4=K就可以了。
所以，如果输入N和K，只要符合N*N=4K就可以判断为YES。
不知道是不是我的理解简单化了？

不好意思，是我的理解简单话了，只考虑了一种平分的情况，呵呵。
不过按这个思路，要使上面等式成立，x、y之间应该有个范围限制吧？不知道是不是可以从那里入手？

我错了，原来可以分多组。没看清题目：（

胜在简单高效

不知道对不对
在附件图片里

另一個地方回復