为了促进各部门员工的交流,百度 (baidu) 举办了一场全公司范围内的 " 拳皇友谊赛 " ,负责组织这场
比赛的是百度的超级 " 拳皇 " 迷 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)
输出
对输入的 N,K 如果 N 个员工通过一定的分组方式可能会一共需要 K 场比赛,则输出 "YES", 否则输出
"NO", 每组数据占一行。
所有的输入输出均为标准输入输出。
例子
输入文件 :
20
21
31
32
输出 :
YES
YES
NO
以下是源代码，解此题在人数为N的情况下，对所有的人首先进行分组，并把所有可能的分组存储起来。
接着依次取出分组，对每个分组进行分析，比较每个分组所需比赛的场次是否为题目要求的K，无论是否
是K都保存输出结果，在最后进行输出。
我在分组的时候，有一些是重复的组，比如6个人的话，3，2，1和1，2，3是同一个分组，但我的程序没
有隔离出来，两种情况都需要计算，这样导致效率的下降。自已也没想到什么好办法解决，但这并不影响
程序的正确性。等以后想到了，再贴出来！
#include <iostream>
#include <vector>
#include <list>
#include <fstream>
using namespace std;
list<vector<int> > groups;
vector<string> res;
char yes[4]={'Y','E','S'};
char no[4]={'N','O'};
void divideGroup(int n, vector<int> gp)
{
if(n==0)
{
groups.push_back(gp);
return;
}
for(int i=1; i<=n; i++)
{
gp.push_back(i);
divideGroup(n-i, gp);
gp.pop_back();
}
return;
}
bool checkCpnNum(const vector<int> &v,int k)
{
int num=0;
for(int i=0; i< v.size(); i++)
for(int j= i+1; j<v.size(); j++)
num+= (v[i]*v[j]);
if(num==k) return true;
return false;
}
bool analyzeGroup(int k)
{
vector<int> v;
int sz;
sz= groups.size();
for(int i=0; i< sz; i++)
{
v= groups.front();
groups.pop_front();
if(checkCpnNum(v, k))
{
groups.clear();
return true;
}
}
return false;
}
void process(int n, int k)
{
vector<int> gp;
divideGroup(n, gp);
cout<<groups.size()<<endl;
string str;
if(analyzeGroup(k))
{
str=yes;
res.push_back(str);
}
else
{
str=no;
res.push_back(str);
}
}
int main()
{
ifstream in("input.txt");
int N, K;
while(in>>N>>K)
process(N,K);
for(int i=0; i< res.size(); i++)
cout<<res[i]<<endl;
}