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分。
/*
我的思路
1:
    0
2:
    0
    1x1+0=1
3:
    0
    1x2+0=2
    1x2+1=3
4:
    0
    1x3+0=3
    1x3+2=5
    1x3+3=6
    2x2+0=4    //最小含2
5:
    1x4+0=4
    1x4+3=7
    1x4+5=9
    1x4+6=10
    2x3+0=6 //最小含2

算法
    数为N
        0
        1x(N-1)+(N-1)可能组合
        2x(N-2)+(N-2)不含1的所有可能组合
        3x(N-3)+(N-2)不含1,2的所有可能组合
        ............................................
        至
        N/2+(N-N/2)+(N-2)不含1,2的所有可能组合
我想的算法启动速度比较慢,但是用了缓冲,一旦计算过大的计算小的就很快了.
应该有更好的算法,但是我没想到...........

张沈鹏 [e-mail]
2007-5-13
*/

#include ＜fstream>
#include ＜sstream>
#include ＜iostream>

#include ＜vector>
#include ＜map>
#include ＜list>

#include ＜string>

#include ＜algorithm>
#include ＜functional>

using namespace std;

#define BEG_END(c)        (c.begin()),(c.end())

typedef unsigned int uint;



template ＜class T>
vector＜T>    possible_NO(T x)
{
    vector＜vector＜T> >    temp=impl_possible_NO(x);
    vector＜T>    res;
    for( vector＜vector＜T> >::iterator i=temp.begin(),end=temp.end();i!=end;++i){
        for( vector＜T>::iterator j=i->begin(),end=i->end();j!=end;++j){
            res.push_back(*j);   
        }
    }
    return res;
}

template ＜class T>
vector＜vector＜T> >    impl_possible_NO(T x)
{
    vector＜vector＜T> >    res;
    vector＜T> temp;

    if (2>x)
    {
        temp.push_back(0);
        res.push_back(temp);
        return res;
    }
    if (2==x)
    {
        temp.push_back(1);
        res.push_back(temp);
        return res;
    }
    static map＜T,vector＜vector＜T>>    > buffer;
    map＜T,vector＜vector＜T> >    >::iterator a=buffer.find(x);
    if (a!= buffer.end() )
        return a->second;

    for (T i=1;x/2>=i;++i)
    {

        vector＜vector＜T> >    N_i=impl_possible_NO(x-i);

        temp.clear();
       
        T base=i*(x-i);
      
        temp.push_back(base);

        if (i＜=N_i.size())
        {
            for (vector＜T>::iterator j=N_i[i-1].begin(),end=N_i[i-1].end();j!=end;++j)
            {
                temp.push_back(base+*j);
            }
        }
        res.push_back(temp);
    }

    buffer[x]=res;

    return res;
}

template ＜class T>
bool possible(T n,T k)
{
    if(k==0)return true;
    if(k＜n-1 || k>n*n-1/2 )return false;

    vector＜T> possibleNo=possible_NO(n);
    if(find(possibleNo.begin(),possibleNo.end(),k)!=possibleNo.end())    return true;
  
    return false;
 
}


int main()
{
    string infile_name="in.txt" , outfile_name="out.txt";

    //ofstream outfile(outfile_name.c_str());
    ostream& outfile = cout;

    ifstream infile(infile_name.c_str());
    if (!infile)
    {
        cerr＜＜"Error : can't open input file "＜＜infile_name＜＜" .\n";
        return -1;
    }

    string line;

    while (getline(infile,line))
    {
        uint n,k;

        istringstream(line)>>n>>k;

        outfile＜＜ (possible(n,k)? "YES":"NO")  ＜＜'\n';
    }

    return 0;
}

评论

1 楼 likeblood 2007-06-07  

比赛规则我看懂了，但是没看懂要问什么