題目+我的解答打包下載
http://www.shnenglu.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的所有可能組合
我想的算法啟動速度比較慢,但是用了緩沖,一旦計算過大的計算小的就很快了.
應該有更好的算法,但是我沒想到...........

張沈鵬 zsp007@gmail.com
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;
}