游子的博客
慈母手中线,游子身上衣, 临行密密缝,意恐迟迟归, 谁言寸草心,报得三春晖。 数据读取中,请稍候......
posts - 337,  comments - 546,  trackbacks - 0

 

/*3.变态比赛规则
为了促进各部门员工的交流,百度举办了一场全公司范围内的“拳皇”(百度内部最流行的格斗游戏)友谊赛,负责组织这场比赛的是百度的超级“拳皇”迷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<N<=500, K>=0)。例:
2 0
2 1
3 1
3 2

 

输出要求:
对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K,则输出"YES",否则输出"NO"
(请全部使用大写字母),每组数据占一行。例:
YES
YES
NO
YES

*/
/*
算法分析:采用递归的方法,原理较简单,大家看源码即可。
*/

/*
  Name:
  Copyright:
  Author:
  Date: 27-05-06 15:37
  Description:
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 100;
void Readata(const char *filename);
bool check(long n, long k);

int main()
{
 time_t startTime;
 time_t endTime;
 time(&startTime);

 Readata("in.txt");

 time(&endTime);
 cout << difftime(endTime, startTime) << endl;

 getchar();
 return 0;
}

void Readata(const char *filename)
{
      fstream in(filename);
      if (!in)
            return ;   //结束程序执行

      while (!in.eof())
      {
            long data[2];

            in >> data[0];
            in >> data[1];
            //cout << data[0] << ' ' << data[1] << endl;

            if (check(data[0], data[1]))
                  cout << "YES" << endl;
            else
                  cout << "NO" << endl;
      }

    in.close(); //关闭文件
}
bool check(long n, long k)
{
    bool flag = false;
    int i;
    if(k == 0) //可能  。。。1
        return true;
    if(n==0 && k || k<0)  //不可能 。。。2
        return false;
    for(i=1; i<n && !flag; i++) //i表示将被减掉的小组的人数,每少一个由i个人组成的组就会少(n-i) * i场比赛
        flag = check(n-i,k - (n-i) * i);  //不断的减少小组数和对应减少的比赛次数,直到出现1或2的情况 (出现可能的情况也会终止分析)
    return flag;
}

posted on 2006-05-31 17:01 游子 阅读(239) 评论(1)  编辑 收藏 引用 所属分类: 软件

FeedBack:
# re: 转载三----我解百度之星题目之" 变态比赛规则 "
2007-05-23 13:07 | optimistic
你不认为递归层数过大会爆栈的吗?  回复  更多评论
  
只有注册用户登录后才能发表评论。

欢迎大家扔鸡蛋!送鲜花!

博客可以收入过千吗?

<2014年6月>
日一二三四五六2526272829303112345678910111213141516171819202122
232425262728293012345

常用链接

留言簿(8)

随笔分类(314)

随笔档案(337)

文章分类(7)

文章档案(10)

相册

收藏夹(1)

其它

友情链接

数字电视

生活、旅游

自己的链接

计算机

搜索

  •  

积分与排名

  • 积分 - 403612
  • 排名 - 9

最新评论

阅读排行榜

评论排行榜