数学建模社区-数学中国

标题: 2006 年百度之星程序设计大赛初赛题目 3 [打印本页]

作者: 厚积薄发 时间: 2010-5-6 18:54
标题: 2006 年百度之星程序设计大赛初赛题目 3
**的比赛规则

为了促进各部门员工的交流，百度 (baidu) 举办了一场全公司范围内的 " 拳皇友谊赛 " ，负责组织这场比赛的是百度的超级 " 拳皇 " 迷 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)

输出

对输入的 N,K 如果 N 个员工通过一定的分组方式可能会一共需要 K 场比赛，则输出 "YES", 否则输出 "NO", 每组数据占一行。

所有的输入输出均为标准输入输出。

例子

输入样例

, V& I* b1 @' N) L/ y1 A+ J( C

& d' ^+ y  F! X3 \' |2 0 5 v& i, T7 P. q+ x

# Z! @: @% H3 d* Z# f$ l6 \2 1
& p; K: C! @5 }
+ `, s5 `5 D  J* g3 1 ' U5 [3 E+ p, j; S( R

7 M) p) b: ^0 G9 W' O6 q: r' r# U. |3 2
8 y$ W5 L  P. Y% V9 a. [2 w

输出样例

' o8 D! T* W. W; i) d
0 w/ ^5 {. O( O8 [% u% M, J7 L
YES
, e* L4 M9 [, J% E; o* \# R( N9 D6 \# h, b' u7 N! K
YES : T! A8 K$ W- G, c: G( c8 d$ T3 b
( M# G' v) F( T4 m
NO : V9 V' Z6 w# L' L
1 F9 W+ L: ~7 b( r5 q% M8 @
YES ! z# a3 F# p) h8 j2 }3 [
example1：

1 w% `* ~. H% i. _. G
#include <cstdlib>% y3 J  l* f# o
#include <iostream>
8 R+ ~" E0 d; [+ V( A: T#include <fstream>
  f) r6 n# H) X3 `7 J#include <cmath>0 h8 x$ c& X& w8 o$ |# y) c  X
using namespace std;
, a# Y% |' a: E" ]) p% |6 R/ z3 C- V6 y( _3 `

3 g$ Y& X3 k8 n( L9 ]3 |4 L: ^bool bt(int N,int K,int min,int count)! P! J! b% t; y6 z' h/ D/ R3 d
{0 X! {: t* @; k1 y) H4 w9 {
   //cout<<N<<"|"<<min<<"|"<<count<<endl;/ I( N8 q( w8 Z' Z+ }7 Y2 B; h# i4 e
   for(int i=min;i<=(N+1)/2;i++)//zhu1 i
% S. _1 w2 |+ ]% A! }8 } {
, U, R! T2 L' d$ u( h       int tmpc=count;, K8 Q, \6 d; V2 K) x
      for(int j=0;j<i;j++): h. V+ @7 Q1 i; [. i8 }
      tmpc+=N-i;
0 X, E; ?& b4 W4 D6 Z       if(tmpc==K)return true;5 Z0 [/ d; z7 b: K( s
      //zhu2 N-i
; B) C/ u& k. ^" G/ S       if(bt(N-i,K,i,tmpc))return true;
# V0 L$ R" |" Q5 N5 V4 O }
' b+ `+ z8 ~: s( J& ?# {: V return false;
, o( j8 a- S* a* N+ Q2 o9 G! [ }
: D- m. M4 F) @" F9 Cint main(int argc, char *argv[])8 N: e$ r& O  `" ^! x
{* f+ j5 ^: f/ K, a: t+ d) M( N
//ifstream inf("input.txt");- x" c: r0 e9 T+ b' Z( C0 O
string str;$ _) ?) L1 G2 e/ X# e
int N,K;1 `9 Z3 \8 G  _' S- e
int count;& d- r. m2 Q, X- C, ]' @
//getline(inf,str);: T9 c8 s" P% V$ t/ z
getline(cin,str);# S" {- ?5 U, V" W# ?8 a# T
sscanf(str.c_str(),"%d %d",&N,&K);
3 M1 @  X. C, o. S if(bt(N,K,1,0))cout<<"YES"<<endl;- P8 ^8 z! c6 ?& y  n
else cout<<"NO"<<endl;
0 c( v" E0 ^% k8 v  b system("PAUSE");; c+ _) F; U; p+ T1 N$ m+ x7 E0 o
return EXIT_SUCCESS;
* M8 G1 _+ Z7 [% F5 |}
* k8 t- O5 B# J  yexample2：

//============================================================================
// Name       : 1.cpp
// Author    : Xusen Yin
// Version    :
// Copyright : Your copyright notice
// Description : **的规则
//=========================================================================
#include <iostream>
#include <bitset>
using namespace std;
#define MAX 128
int main(){
int n = 0,k = 0;
bitset<MAX> bAssert;
cout << "请输入 N K (以－1 , -1结束)：" << endl;
size_t j = 0;
while(1){
      cin >> n >> k;
      if(n == -1 || k == -1)
         break;
      for(int i = 0 ; i <= n/2 ; i++)
         if(i * (n - i) == k){
            //是OK的
            bAssert.set(j);
            break;
         }
      j++;
}
for(size_t i = 0 ; i <= bAssert.count() ; i++){
      if(bAssert.test(i))
         cout << "YES" << endl;
      else
         cout << "NO" <<endl;
}
return 0;
}

example3：
import java.io.IOException;
import java.util.Random;

public class BtRaceRule
{
private static int p_number;//人数
private static int r_number;// 比赛场数
public static void logic(int n,int m)
{
      int flag = 0;
      for(int i=0;i<=n/2;i++)
      {
         int j = n-i;
         if(i*j==m)
         {
            flag = 1;
         }
      }
      if(flag==1)
      {
         System.out.println("Yes");
      }
      else
      {
         System.out.println("No");
      }
}
public static void main(String[] args) throws IOException
{
      BtRaceRule[] rule = new BtRaceRule[10];
      GetData data = new GetData();
      System.out.println("输入比赛人数和可能的比赛场数：");
      Random r = new Random();
      for(int i=0;i<rule.length;i++)
      {
         rule.p_number=Math.abs(data.integer());
3 I1 X* S( J( v. P/ ~
+ I, x1 q- t0 D# j          rule.r_number=Math.abs(data.integer());
4 F1 n* e; N. m' K" G' m       6 s2 V; D% s6 o- F' |* V( z
         System.out.println(rule.p_number+" "+rule.r_number);  ^/ C0 t6 }1 S5 u6 F) U$ g
         //输出一组分组和可能的比赛次数
7 P: T- h! E& I; p+ x( j7 v- K          logic(rule.p_number,rule.r_number);
         //逻辑判断，并输出结果  yes or no
  t/ S+ ], M0 [6 r- Z! u       }
0 b1 P) a. I" z8 S+ s# {' t }1 c1 f: p& ]: ]7 E- d2 T5 [
}
作者: hangdao 时间: 2011-1-13 10:58
这是什么东东~~~~
作者: gbqje 时间: 2011-8-18 16:31
顶你一下，好贴要顶！$ A+ X0 _  i" |

' L, ]- _+ \  g5 V& ~( @. a  oIT9学院站，它的宗旨是为广大电脑爱好者提供学习和交流的平台可以学到国内最齐全的电脑技术，学习的电脑知识门类齐全，教学兼备；能在线学习电脑技术，并且设有论坛交流中心，是国内优秀电脑技术学习基地。
3 _0 z" y2 G) R5 B3 f' S8 s
, @; d2 ^9 H, h0 }2 C- ]IT9学院网络，一个专为您量身定做的优秀平台。 4 d: T2 G" j9 n/ D5 H7 X6 f
& `8 n0 i) k) U% U
IT9学院it9.com/ 一直致力于为广大电脑知识爱好者提供全面、专业、权威的软件使用教程，如网络软件、系统工具、聊天工具、编程开发、图形图象等各种软件应用、技巧以及解决方案等，是大家学习专业计算机知识的最佳场所。
2 y' @* ~# v! s: T3 N! d7 |% h4 @0 _' g0 ]) @; }+ D+ a3 y& V3 y9 O
国内最齐全的电脑技术学习基
4 S1 Y. G$ o: c# Q6 W
% s8 }  r( h$ m7 {IT9学院站是国内最齐全的电脑技术学习网站，他的教学课程门类齐全，应有尽有，完全覆盖了从基础到高端教与学的知识面，不但适合广大电脑兴趣爱好者进行知识普及，还非常适合大中专院校学生和电脑科技从业人员专业知识技能提升和交流。
2 b7 P- O7 I  ]6 p( N
# a; z" |+ p7 k/ Y$ }IT9学院教授课程内容包括办公应用、图形处理与设计、网吧技术、攻防专区、编程开发、网站建设与开发、系统专区等。每个大类专区又细分小类，如办公应用专区细分Powerpoint教程、Excel教程、Outlook教程、Word教程、FruityLoops教程、Reason教程。系统专区细分C#教程、java教程、VB教程、Jsp教程、Asp教程、VC教程、易语言教程、Php教程等等。IT9学院提供图文，视频教程，甚至在线交流等方式开展教学，是一个门类齐全、内容详尽、直观易懂的网络课堂。
. A2 d& U! l& j' F
% A; w2 z/ O$ z# m, t门类齐全，教学兼备 ; _* y; X. u1 e$ ?  B2 n+ P6 |( p
- y2 T& R" W; E4 @3 X
对于电脑爱好者来说，IT9学院开设的视频教程区为其提供网上直观的操作与视频演示，并提供了详细的大中专院校客座教授在线教学，可谓门类齐全教学兼优，同时IT9学院网不仅设有工具发布区、软件资源区、黑客软件区等工具类下载栏目，同时还配套设置了数码资讯、硬件交流区、软件交流区、疑难解答区、贵宾学习区、免费资源区、视频教程区等，可谓教学兼备，边学边实践，真正做到了动手，动脑学习。
$ M2 J7 \3 s* F
: ?" W8 ~$ O  D6 z, BIT9学院站不仅可以在线学习电脑技术知识，而且还设有论坛交流中心 bbs.it9.com 和软件下载. 提供各位电脑爱好者或提问或分享经验等交流，在这里不论你是大虾还是菜鸟，都能找到你想要的东西，下载到你想要的软件.提高你具备的本领，同时也能分享你在计算机领域的“成就”，因为我们是IT9学院，一个真正为广大电脑爱好者提供学习和交流的平台。 # b* i( S: f: t

- l' I* N" \/ U- N  G由腾讯、网易、新浪.admin5站长论坛共同推荐的电脑学院技术站：
8 m2 J( N, ]( s. K2 T& e. D; L5 R8 G  F* h
腾讯digi.tech.qq.com/a/20110601/001268.htm
4 Y2 b9 Q8 J; a% x( Z网易 news.163.com/11/0602/11/75HPKJ0U0001125P.html 9 }* w) Q  |( ^' m) q# J
新浪 finance.sina.com.cn/roll/20110602/12219937561.shtml
2 [! b3 n; `* KA5：bbs.admin5.com/thread-2686329-1-1.html 3 R8 [7 b% c' D: w( |
IT9网络学院：it9.com
作者: qo1211 时间: 2011-8-31 14:22
百度算法大赛的题目~O~反正我目前是编不出来
作者: 神Y殇 时间: 2011-10-15 21:45
..................................$ I1 T, m% S: V$ s" p

; R; P) @0 P. |# z' ~
0 w  g: y7 `' ~
( P  U, s" F+ w
$ x- }0 ^) {7 X' t, m% J; o0 z
# g$ l# ^0 L" }. e7 f' v3 r) L& U; \4 |$ g5 W* D* P7 F
/ J; K6 V: e8 T* E  W3 T" K( `% C
) T' C- Q% o  E4 u3 G, I% ]$ k- b

4 _4 O- a8 H6 N) A* I. Z) e! P9 \5 F9 n& }! ]

* z4 q2 @$ x: P; {1 i9 Z! l
" G$ z- ~$ c/ ~+ L* F51koo.net黑客论坛　soyangsyl.com搜羊娱乐新闻网
作者: ehi28 时间: 2011-12-11 16:23
嗯,不错,支持一下.
+ T, f% I9 Q' t1 l
作者: schnee 时间: 2012-2-6 17:33
顶！！！！！！！
作者: laogao598 时间: 2012-4-29 10:23
顶！！！！！！！

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5