题目+我的解答打包下载
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的所有可能组合
我想的算法启动速度比较慢,但是用了缓冲,一旦计算过大的计算小的就很快了.
应该有更好的算法,但是我没想到...........

张沈鹏 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;
}
 



posted on 2007-05-15 10:54 张沈鹏 阅读(1299) 评论(3)  编辑 收藏 引用 所属分类: C++
Comments
  • # re: 2006百度之星程序设计大赛试题-变态比赛规则(解答)
    sundrop
    Posted @ 2008-05-22 04:37
    按照你的思路写的程序 好像是动态规划
    不过程序的输入输出和题目要求稍有出入
    程序里用了 set 和 hash_map
    并且缓存结果集以提高性能
    函数返回值用指针以减少拷贝
    可以算到 n=120 的情况
    再打的话 内存就不够用了
    仅供参考

      回复  更多评论   
  • # re: 2006百度之星程序设计大赛试题-变态比赛规则(解答)
    sundrop
    Posted @ 2008-05-22 04:39
    /*
    * Combat Game
    *
    * n players are divided into g groups.
    * Players in one group do not combat with each other.
    * Every two players from different groups should combat with each other.
    * How many combats there will be between these g groups?
    *
    * n is the total player number, n belong-to N,
    * g is the total group number, 1 <= g <= n.
    *
    * k(n, g) is the combat number if
    * n players are divided into g groups.
    *
    * k(n, g) = K(n, g, 1)
    *
    * K(n, g, r) is the combat number if
    * n players are divided into g groups,
    * and at least, r players should be in each group.
    *
    * K(n, g, r) = {
    * set-item:
    * m*(n-m) + K(n-m, g-1, m)
    * condition:
    * |-> m belong-to N,
    * |-> r <= m <= n/g
    * }
    * K(n, g, r) = { null-set |-> r > [n/g] }
    * K(n, 1, r) = { 0 |-> r <= n }
    */
    vector_ptr calc_k(size_t n, size_t g, size_t r) {
    #ifdef DEBUG
    cout << "\tcalc_k: " << n << ", " << g << ", " << r << endl;
    #endif
    if (r > n/g) {
    return 0;
    }
    vector_ptr v = alloc_vector(n, g, r);
    if (v->size() != 0) {
    return v;
    }
    if (g == 1) {
    PUSH_(*v, 0);
    return v;
    }
    vector_ptr t;
    for (size_t m = r, tm; m <= n/g; ++m) {
    #ifdef DEBUG
    cout << "\tm = " << m << endl;
    #endif
    tm = m*(n-m);
    t = calc_k(n-m, g-1, m);
    if (t != 0) {
    #ifdef DEBUG
    cout << "\t(" << (n-m) << ", " << (g-1) << ", " << m << ") => { ";
    copy(t->begin(), t->end(), ostream_iterator<size_t>(cout, " "));
    cout << " }" << endl;
    #endif
    typedef vector_t::iterator IterT;
    for (IterT it = t->begin(); it != t->end(); ++it) {
    PUSH_(*v, tm + *it);
    }
    } else {
    PUSH_(*v, tm);
    }
    }
    return v;
    }

    /*
    * Read number n, as the total player number.
    * Output combat numbers if
    * these n players is divided into 1, 2, ..., n groups.
    *
    * The program will terminate if read an zero.
    */
    int main() {
    #ifdef DEBUG
    cout << "Program is running in DEBUG mode.\n\n";
    #endif
    #ifdef DEBUG_MEMORY_USAGE
    cout << "Program is running in DEBUG_MEMORY_USAGE flag mode.\n\n";
    #endif
    size_t n;
    vector_ptr v;
    while(true) {
    cout << "Please input total player number (type 0 to quit) : ";
    cin >> n;
    cout << endl;
    if (n == 0) {
    release();
    break;
    }
    for (size_t g = 1; g <= n; ++g) {
    #ifdef DEBUG
    cout << "n = " << n << ", g = " << g << endl;
    #endif
    v = calc_k(n, g, 1);
    if (v != 0) {
    cout << "(" << n << ", " << g << ") => { ";
    #ifndef DEBUG_MEMORY_USAGE
    copy(v->begin(), v->end(), ostream_iterator<size_t>(cout, " "));
    #else
    cout << "set with size = " << v->size();
    #endif
    cout << " }" << endl;
    } else {
    cout << "(" << n << ", " << g << ", " << 1 << ") => null-set" << endl;
    }
    }
    cout << endl;
    }
    system("pause");
    return 0;
    }  回复  更多评论   
  • # re: 2006百度之星程序设计大赛试题-变态比赛规则(解答)
    sundrop
    Posted @ 2008-05-22 04:40
    上个程序 之前的部分

    #include <cstdlib>
    #include <iostream>
    #include <iterator>

    #include <deque>
    #include <set>
    #include <map>
    #include <ext/hash_map>

    using namespace std;
    using namespace __gnu_cxx;

    /*
    * define DEBUG macro to enable debug message
    *
    *
    #define DEBUG
    //*/

    /*
    * define DEBUG_MEMORY_USAGE macro to show memory usage info
    *
    *
    #define DEBUG_MEMORY_USAGE
    //*/

    /*
    * define USE_SET to use std::set as default container
    * undefine USE_SET to use std::deque as default container
    */
    #define USE_SET
    //*/

    #ifdef USE_SET
    typedef set<size_t> vector_t;
    #define PUSH_(CONT, VALUE) (CONT).insert(VALUE)
    #else
    typedef deque<size_t> vector_t;
    #define PUSH_(CONT, VALUE) (CONT).push_back(VALUE)
    #endif

    typedef vector_t * vector_ptr;

    typedef struct key_type {
    size_t n, g, r;
    key_type(size_t pn, size_t pg, size_t pr) :
    n(pn), g(pg), r(pr) {
    }
    bool operator <(key_type const & that) const {
    return (n < that.n && g < that.g && r < that.r);
    }
    bool operator ==(key_type const & that) const {
    return (n == that.n && g == that.g && r == that.r);
    }
    } key_t;

    namespace __gnu_cxx {
    template<> struct hash<key_t>
    { size_t operator()(key_t const & __x) const { return __x.n*10000+__x.g*100+__x.r; } };
    }

    typedef hash_map<key_t,vector_ptr> map_t;

    map_t storage;

    #ifdef DEBUG_MEMORY_USAGE
    size_t created = 0, deleted = 0;
    #endif

    vector_ptr alloc_vector(size_t n, size_t g, size_t r) {
    typedef map_t::iterator mIterT;
    key_t const ky(n, g, r);
    mIterT it = storage.find(ky);
    vector_ptr ptr;
    if (it == storage.end() || !(it->first == ky)) {
    ptr = new vector_t();
    storage.insert(make_pair(ky, ptr));
    #ifdef DEBUG
    cout << "\tcreate (" << n << ", " << g << ", " << r << ")" << endl;
    #endif
    #ifdef DEBUG_MEMORY_USAGE
    created += 1;
    #endif
    } else {
    ptr = it->second;
    }
    return ptr;
    }

    void release() {
    #ifdef DEBUG_MEMORY_USAGE
    map<size_t, size_t> statistic;
    #endif
    typedef map_t::iterator mIterT;
    for (mIterT it = storage.begin(); it != storage.end(); ++it) {
    delete it->second;
    #ifdef DEBUG_MEMORY_USAGE
    deleted += 1;
    if (statistic.find(it->first.n) == statistic.end()) {
    statistic[it->first.n] = 0;
    }
    statistic[it->first.n] += 1;
    #endif
    }
    #ifdef DEBUG_MEMORY_USAGE
    cout << "created " << created << endl;
    for (map<size_t, size_t>::iterator its = statistic.begin();
    its != statistic.end(); ++its) {
    cout << "\tn = " << its->first << ", object number = " << its->second << endl;
    }
    cout << "deleted " << deleted << endl;
    #endif
    }
      回复  更多评论   

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理