題目+我的解答打包下載
http://www.shnenglu.com/Files/zuroc/kof_rule.zip變態(tài)比賽規(guī)則

為了促進(jìn)各部門(mén)員工的交流，百度舉辦了一場(chǎng)全公司范圍內(nèi)的“拳皇”（百度內(nèi)部最流行的格斗游戲）友誼賽，負(fù)責(zé)組織這場(chǎng)比賽的是百度的超級(jí)“拳皇”迷W.Z。W.Z不想用傳統(tǒng)的淘汰賽或者循環(huán)賽的方式，而是自己制定了一個(gè)比賽規(guī)則。

由于一些員工（比如同部門(mén)或者相鄰部門(mén)員工）平時(shí)接觸的機(jī)會(huì)比較多，為了促進(jìn)不同部門(mén)之間的交流，W.Z希望員工自由分組。不同組之間的每?jī)蓚€(gè)人都會(huì)進(jìn)行一場(chǎng)友誼賽而同一組內(nèi)的人之間不會(huì)打任何比賽。

比如4個(gè)人，編號(hào)為1~4,如果分為兩個(gè)組并且1，2一個(gè)組，3，4一個(gè)組，那么一共需要打四場(chǎng)比賽：1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如

果是1，2，3一組，4單獨(dú)一組，那么一共需要打三場(chǎng)比賽 1 vs 4，2 vs 4，3 vs 4。


很快W.Z意識(shí)到，這樣的比賽規(guī)則可能會(huì)讓比賽的場(chǎng)數(shù)非常多。W.Z想知道如果有N個(gè)人，通過(guò)上面這種比賽規(guī)則，總比賽場(chǎng)數(shù)有可能為K場(chǎng)嗎？

比如3個(gè)人，如果只分到一組則不需要比賽，如果分到兩組則需要2場(chǎng)比賽，如果分為三組則需要3場(chǎng)比賽。但是無(wú)論怎么分都不可能恰需要1場(chǎng)比賽。


相信作為編程高手的你一定知道該怎么回答這個(gè)問(wèn)題了吧？ 那么現(xiàn)在請(qǐng)你幫助W.Z吧。


輸入要求：
每行為一組數(shù)據(jù)，包含兩個(gè)數(shù)字 N, K(0N=500, K=0)。例：
2 0
2 1
3 1
3 2
樣例：in.txt



輸出要求：
對(duì)輸入的N,K 如果N個(gè)員工通過(guò)一定的分組方式可以使比賽場(chǎng)數(shù)恰好為K，則輸出YES，否則輸出NO（請(qǐng)全部使用大寫(xiě)字母），每組數(shù)據(jù)占一行。例：
YES
YES
NO
YES
樣例：out.txt


評(píng)分規(guī)則：
1．程序?qū)⑦\(yùn)行在一臺(tái)Linux機(jī)器上（內(nèi)存使用不作嚴(yán)格限制），在每一測(cè)試數(shù)據(jù)集上運(yùn)行不能超過(guò)10秒，否則該用例不得分；
2．要求程序能按照輸入樣例的格式讀取數(shù)據(jù)文件，按照輸出樣例的格式將運(yùn)行結(jié)果輸出到標(biāo)準(zhǔn)輸出上。如果不能正確讀入數(shù)據(jù)和輸出數(shù)據(jù)，該題將不得分；
3．該題目共有3個(gè)測(cè)試數(shù)據(jù)集，每個(gè)測(cè)試數(shù)據(jù)集為一個(gè)輸入文件。各測(cè)試數(shù)據(jù)集占該題目分?jǐn)?shù)的比例分別為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

算法
    數(shù)為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的所有可能組合
我想的算法啟動(dòng)速度比較慢,但是用了緩沖,一旦計(jì)算過(guò)大的計(jì)算小的就很快了.
應(yīng)該有更好的算法,但是我沒(méi)想到...........

張沈鵬 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;
}