主题：百度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个回复）
沙发
if007 [专家分：650] 发布于 2006-05-28 03:15:00
#include <iostream.h>
#include <math.h>
/*
文件描述： 解百度赛题3
创建人： 陈泽丹
版本号： 1.0
修改次数： 0
*/
const int Max=1000;
int tot[Max];
int pt=-1;
int check(int N, int temp, int p)
{
int sum=temp;
for (int i=0; i<=p; i++)
sum+=tot[i];
if (sum == N) return 1;
return 0;
}
int fun(int N, int K)
{
if (K==0) return 1;
int i, sq=sqrt(K), temp;
for (i=1; i<=sq; i++)
{
temp=K/i;
if (K%i == 0)
{
pt++;
tot[pt]=i;
}
if (check(N, temp, pt)) return 1;
}
return 0;
}
void main()
{
int N,K;
cin>>N;
cin>>K;
if ( fun(N,K) ) { cout<<"YES"<<endl; }
else { cout<<"NO"<<endl; }
}
板凳
if007 [专家分：650] 发布于 2006-05-28 04:34:00
...不好意思,虽然用例子的数据测试后都正确,但以上算法是错误的,至于改良方法,还没想到 ...^-^!...
3 楼
goal00001111 [专家分：4030] 发布于 2006-05-28 12:18:00
/*
算法分析：
1。用数组total[]存储可能存在的比赛场数。
2。顺序分析把n个人分成2-（n-1）个组的情况，即顺序分析k= 2-（n-1）
A 用数组fenfa[]存储分成k组时各种不同组合的比赛场数，用数组part[]存储存储具体的组合情况，
即每组有多少人 。
B 将问题“求把n个人分成k组时各种不同组合的情况”转化为：
将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)，
例如:n=7,k=3,下面三种分法被认为是相同的。
1，1，5； 1，5，1； 5，1，1；
求各种不同分法的组合。
C 把求得的各种不同分法的组合存储到数组part[]中。再根据数组part[]计算每种组合的比赛场数。
D 把每种组合的比赛场数存储到数组fenfa[]中。
3。按照上面的分析方法，可以产生n-1个一维数组fenfa[]，把每个数组fenfa[]的值存储到数组total[]。
4。根据输入数据，在数组total[]中进行分析判断。
*/
#include <iostream>
#include<fstream>
#include <time.h>
using namespace std;
const int MAX = 100;
void Readata(const char *filename);
void SplitNumber(int n, int k, int step, int part[], int fenFa[], int &top);
int NumGame(const int part[], int low, int high);
int main()
{
time_t startTime;
time_t endTime;
time(&startTime);
Readata("in.txt");
time(&endTime);
cout << difftime(endTime, startTime) << endl;
getchar();
return 0;
}
void Readata(const char *filename)
{
fstream in(filename);
if (!in)
return ; //结束程序执行
while (!in.eof())
{
int data[2];
in >> data[0];
in >> data[1];
//cout << data[0] << ' ' << data[1] << endl;
int *total = new int[data[0]*data[0]*data[0]];//存储可能存在的比赛场数
total[0] = 0;
int t = 1;
for (int k=2; k<=data[0]; k++)//分析各种分组可能产生的比赛场数
{
int *fenFa = new int[k*data[0]];//存储分成k组时各种不同组合的比赛场数
int *part = new int[k+1];//存储具体的组合情况，即每组有多少人
part[0] = 1;//为处理方便，不考虑下标0，并使part[0] = 1
int top = 0;//累积各种不同组合的数量
SplitNumber(data[0], k, 0, part, fenFa, top);//处理各种不同组合的分法
//for (int i=0; i<top; i++)
// cout << fenFa[i] << ' ';
// cout << endl;
for (int i=0; i<top; i++)//存储可能存在的比赛场数
total[t++] = fenFa[i];
delete []part;
delete []fenFa;
}
int i;
for (i=0; i<t; i++) //判断是否可能存在data[1]场比赛
if (data[1] == total[i])
{
cout << "YES" << endl;
break;
}
if (i == t)
cout << "NO" << endl;
delete []total;
}
in.close(); //关闭文件
}
void SplitNumber(int n, int k, int step, int part[], int fenFa[], int &top)
{
if (k == 2)
{
for (int i=part[step]; i<=n/2; i++)
{
if (n-i >= i)
{
part[step+1] = i;
part[step+2] = n-i;
//for (int j=1; j<=step+2; j++)
// cout << part[j] << ' ';
// cout << endl;
fenFa[top++] = NumGame(part, 1, step+2); //存储每种组合的比赛场数
}
}
}
else
{
for (int i=part[step]; i<=n/2; i++)
{
part[step+1] = i;
SplitNumber(n-i, k-1, step+1, part, fenFa, top);
}
}
}
int NumGame(const int part[], int low, int high)//计算每种组合的比赛场数
{
int sum;
if (low == high) //如果只有1个组，比赛场数为0
sum = 0;
else if (low == high-1)//如果有2个组，比赛场数为两组人数的乘积
sum = part[low] * part[high];
else //如果多于2个组，先把多个组合并成两个大组，再递归处理每个大组
{
int mid = (low + high) / 2 ;
int sum1 = 0;
for (int i=low; i<=mid; i++)
sum1 += part[i];
int sum2 = 0;
for (int i=mid+1; i<=high; i++)
sum2 += part[i];
sum = sum1 * sum2;
sum += NumGame(part, low, mid) + NumGame(part, mid+1, high);
}
return sum;
}
4 楼
if007 [专家分：650] 发布于 2006-05-28 12:31:00
哈,so good!
不过偶有种不祥的预感:总觉得这题会有可巧解的地方...
(
晕,一块砖头飞奔而来! 不明白,为什么雅典那可以对圣斗士说她有种不祥的预感,偶就不行呢?
...哈哈...
)
5 楼
yxs0001 [专家分：9560] 发布于 2006-05-28 19:52:00
可以递归
6 楼
yxs0001 [专家分：9560] 发布于 2006-05-28 19:53:00
递归 很简洁
7 楼
eastcowboy [专家分：25370] 发布于 2006-05-28 20:48:00
简洁的估计不行，狂剪枝吧。
8 楼
iAkiak [专家分：8460] 发布于 2006-05-28 20:56:00
500 1
大约要5秒
9 楼
wbhyb [专家分：60] 发布于 2006-05-29 00:24:00
#include <iostream>
#include <time.h>
using namespace std;
int PB3(long N, long K)
{
long ii, TK;
if (N == 1) if (K == 0) return 1; else return 0;
TK = N*(N-1)/2;
if (K > TK) return 0;
if (K == TK) return 1;
if (K == 0) return 1;
for (ii=(N-1);ii>0;ii--)
{
TK = K - ii*(N-ii);
if (TK == 0) return 1;
if (TK < 0) return 0;
if (PB3(N-ii, TK)) return 1;
}
return 0;
}
int main()
{
long N, K, Result, ii;
clock_t Start, End;
while(1)
{
cout<<"Input N and K: "; cin>>N>>K;
if (!N) break;
Result = PB3(N,K);
if (Result)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
/*
while(1)
{
cout<<"Input N: "; cin>>N;
if (!N) break;
K = N*(N-1)/2 + 1;
Start = clock();
for (ii=0;ii<K;ii++) Result = PB3(N,ii);
End = clock();
cout<<"Time = "<<(double)(End - Start)/CLOCKS_PER_SEC<<endl;
}
*/
return 0;
}
10 楼
flymouse [专家分：0] 发布于 2006-05-29 00:38:00
DP
我来回复
您所在位置：