百度之星 变态的比赛规则

变态的比赛规则

为了促进各部门员工的交流，百度 (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=0)

输出

对输入的 N,K 如果 N 个员工通过一定的分组方式可能会一共需要 K 场比赛，则输出 "YES", 否则输出 "NO", 每组数据占一行。

所有的输入输出均为标准输入输出。

例子

输入文件 :

2 0

2 1

3 1

3 2

输出 :

YES

YES

NO

YES

 

这里不能带word公式，只能贴截图了。

 

 

 

附程序：

1，func.cpp。找出N所有可能组合。

 

#include <iostream>

using namespace std;

#define N 5
int dest[N] = {0};

void display(int iTotal, int iCurrent, int iSum)
{
    int iNum = iSum/iCurrent;

    if(iCurrent == 1)
    {
        if(iSum >= dest[iTotal-iCurrent])
        {
            cout << N << "=";
            for(int j=0; j<iTotal-iCurrent; j++)
            {
                cout << dest[j] << "+";
            }
            cout << iSum << endl;
            return;
        }
    }

    int iBegin = (iTotal - iCurrent) > 0 ? dest[iTotal-iCurrent-1] : 1;
    for(int i=iBegin; i<=iNum; i++)
    {
        dest[iTotal-iCurrent] = i;
        display(iTotal, iCurrent-1, iSum-dest[iTotal-iCurrent]);
    }
}


void main()
{
    for(int i=N; i>1; i--)
    {
        display(i, i, N);
    }
}

2，最终代码。main.cpp

 

#include <iostream>

using namespace std;

#define N 9
#define K 23
#define Target N * N - 2 * K
int dest[N] = {0};

void display(int iTotal, int iCurrent, int iSum)
{
    int iNum = iSum/iCurrent;
    
    if(iCurrent == 1)
    {
        if(iSum >= dest[iTotal-iCurrent])
        {
            int iSquareSum = 0;
            for(int j=0; j<iTotal-iCurrent; j++)
            {
                iSquareSum += dest[j] * dest[j];
            }
            iSquareSum += iSum * iSum;

            if(iSquareSum == Target)
            {
                for(int j=0; j<iTotal-iCurrent; j++)
                {
                    cout << dest[j] << ",";
                }
                cout << iSum << endl;
            }
            return;
        }
    }
    
    int iBegin = (iTotal - iCurrent) > 0 ? dest[iTotal-iCurrent-1] : 1;
    for(int i=iBegin; i<=iNum; i++)
    {
        dest[iTotal-iCurrent] = i;
        display(iTotal, iCurrent-1, iSum-dest[iTotal-iCurrent]);
    }
}


void main()
{
    for(int i=N; i>1; i--)
    {
        display(i, i, N);
    }
}