主题：百度Astar2006程序设计大赛预赛题--变态比赛规则
zwj1207
[专家分：40] 发布于 2006-05-27 10:38:00
注册过的朋友请到http://star.baidu.com 答题
3.变态比赛规则
为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛，负责组织这场比赛的是百度的超级“拳皇”迷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(0<N<=500, K>=0)。例：
2 0
2 1
3 1
3 2
输出要求：
对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K，则输出"YES"，否则输出"NO"（请全部使用大写字母），每组数据占一行。例：
YES
YES
NO
YES
评分规则：
1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试数据集上运行不能超过10秒，否则该用例不得分；
2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3．该题目共有3个测试数据集，每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为30%，30%，40%；
4．该题目20分。
回复列表 （共20个回复）
11 楼
yxs0001 [专家分：9560] 发布于 2006-05-29 06:59:00
简洁吧
bool check(long n,long k){
bool flag = true;
int i;
if(k == 0)
return false;//可能
if(n==0 && k || k<0)
return true;//不可能
for(i=1;i<n && flag;i++)
flag &= check(n-i,k - (n-i) * i);
return flag;
}
12 楼
lt19870917 [专家分：750] 发布于 2006-05-29 07:41:00
a1+a2=n;
a1*a2=k;
x^2-nx+k=0的两根是否为整数
13 楼
lt19870917 [专家分：750] 发布于 2006-05-29 07:48:00
算sqrt(n^2-4k)+n是否为偶数,麻烦之处在与要判断n^2-4k是否为完全平方数,需要0(n)
14 楼
yxs0001 [专家分：9560] 发布于 2006-05-29 08:06:00
[quote]a1+a2=n;
a1*a2=k;
x^2-nx+k=0的两根是否为整数[/quote]
这种算法是有局限性的
只能正确处理分两组的情况
反例 n = 5
分3组 1 1 3 比赛次数为 1 + 3 + 3 = 7
x^2 - 5x + 7 = 0很明显没有整数解
15 楼
logway [专家分：10] 发布于 2006-05-29 18:10:00
一行代码解决问题
fin>>n>>k;
if(k==0||k>=n-1&&k<=n*(n-1)/2)cout<<"YES";else cout<<"NO";
16 楼
太没劲了 [专家分：2050] 发布于 2006-05-29 18:35:00
[quote]一行代码解决问题
fin>>n>>k;
if(k==0||k>=n-1&&k<=n*(n-1)/2)cout<<"YES";else cout<<"NO";
[/quote]
@logway，问下 n==9, k==16 有无可能？如果可能，分成几组？怎么分组？
17 楼
goal00001111 [专家分：4030] 发布于 2006-05-29 19:38:00
yxs001:向你致敬!
我根据你的意思做了一个简单的变换和注释,以便理解
bool check(long n, long k)
{
bool flag = false;
int i;
if(k == 0) //可能 。。。1
return true;
if(n==0 && k || k<0) //不可能 。。。2
return false;
for(i=1; i<n && !flag; i++) //i表示将被减掉的小组的人数，每少一个由i个人组成的组就会少(n-i) * i场比赛
flag = check(n-i,k - (n-i) * i); //不断的减少小组数和对应减少的比赛次数，直到出现1或2的情况 （出现可能的情况也会终止分析）
return flag;
}
18 楼
eastcowboy [专家分：25370] 发布于 2006-05-30 02:33:00
我提交的，暴长的代码，感觉挺快的。计算100次 500 1 的情况，眨眼完成了。（我这个算法在K小的时候很好用。）
大家试试这两组数据：
500 123750（YES，分成100堆，每堆为5）
500 93750(YES，分成4堆，每堆125)
#include<stdio.h>
#include<assert.h>
static int N,K;
static int arr[500]; /* 满足：arr[i]<=arr[j]，当i<j */
int Solve(int start, int current)
{
int i,j;
if( current == K )
return 1;
assert( current < K );
j = (arr[start-2]+arr[start-1])/2 + 1;
if( j > arr[start-1] )
j = arr[start-1];
for(i=arr[start-2]; i<=j && i<arr[start-1]; ++i)
{
int save = arr[start-1];
int tmp;
arr[start-1] = i;
arr[start] = save-i;
tmp = current+(save-i)*i;
if( tmp > K )
return 0;
if( Solve(start+1,tmp) )
return 1;
arr[start-1] = save;
}
return 0;
}
int main(int argc, char *argv[])
{
FILE *fin;
fin = fopen(argv[1],"r");
if( !fin )
{
printf("Error: cannot open input file.");
return 1;
}
while( fscanf(fin, "%d%d", &N, &K) != EOF )
{
int i,j;
int found = 0;
//最大剪枝
if( K > (N*(N-1)/2) )
{
printf("NO\n");
continue;
}
else if( K == (N*(N-1)/2) )
{
printf("YES\n");
continue;
}
//分成一组
if( K==0 )
{
printf("YES\n");
continue;
}
//分两组
j = N/2+1;
for(i=1; i<=j; ++i)
{
if( i*(N-i)==K )
{
found = 1;
break;
}
}
if( found )
{
printf("YES\n");
continue;
}
//三组以上
for(i=1; i<=j; ++i)
{
int tmp;
arr[0] = i;
arr[1] = N-i;
tmp = i*(N-i);
if( tmp > K )
break;
found = Solve(2,tmp);
if(found)
break;
}
if( found )
printf("YES\n");
else
printf("NO\n");
}
fclose(fin);
return 0;
}
19 楼
ITER [专家分：680] 发布于 2006-05-30 22:11:00
百家争鸣啊 哈哈 小弟也来提点自己的观点哦:
小弟个人认为此题可以用逆思想,具体如下:
如果要看K场是否可能就先把所有K的因子成对的求出来a1,a2,b1,b2...(a1*a2=K;b1*b2=K...)
然后求(a1+a2=N?b1+b2=N?...)
如果有一对满足i1+i2=N则YES else NO 感觉这样能少求不少
因子很多的K总该不会多吧(希望 哈哈)
20 楼
ITER [专家分：680] 发布于 2006-05-30 22:18:00
而且到某对j1+j2<N 后即可停止
原因:用例子20说明:
因子:1,20,2,10,4,5
越到后面加起来的值越小 所以当某对j1+j2<N后 后面情况都<N 不符合
我来回复
您所在位置：