**的比赛规则
# ]' {1 S! k- j( y8 \
. S$ k2 D; x1 p7 h# L为了促进各部门员工的交流,百度 (baidu) 举办了一场全公司范围内的 " 拳皇友谊赛 " ,负责组织这场比赛的是百度的超级 " 拳皇 " 迷 W.Z. W.Z 不想用传统的淘汰赛或者循环赛的方式,而是自己制定了一个比赛规则。
8 T) j& e6 _4 T* Z0 F
0 D x7 R- q/ ]/ R7 A由于一些员工(比如同部门或者相临部门员工)平时接触的机会比较多,为了促进不同部门之间的交流, W.Z 希望员工自己组成不同组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人则之间不会打任何比赛。 1 l) y. h0 W" D# w
3 L; Y, f. q/ z: R* p# G% m比如 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. 2 o$ U3 w* l0 P1 f% P: m
9 v& b- X# j- T# Y2 [) V% q
很快 W.Z 意识到,这样的比赛规则可能会让比赛的场数非常多。 W.Z 想知道如果有 N 个人 , 通过上面这种比赛规则,总比赛场数有可能为 K 场吗?比如 3 个人,如果只分到一组则不需要比赛,如果分到两组则需要 2 场比赛 , 如果分为三组则需要 3 场比赛。但是无论怎么分都不可能只需要 1 场比赛。
" n. P- y; T' I. X5 `+ _% h$ W4 z+ |! r7 h$ k' o* G$ R
相信作为编程高手的你一定知道该怎么回答这个问题了吧? 那么现在请你帮助 W.Z 吧。
; h. _' s* J: F* J8 A/ J: V' j! `/ g/ n i/ P0 h6 H U
输入 8 r! y# X/ Q' A0 m6 `
3 S! v! r" S% V8 {5 Z2 y每行为一组数据,包含两个数字 N, K 。 (0<N<=500, K>=0)
2 x% O2 c) G( U( x0 Z4 v8 E3 M
4 S5 M" i! ~8 U$ g$ }输出
: i9 U ]2 }7 t+ U$ R& a+ i( J, L5 G% F+ G% G* H; l( x
对输入的 N,K 如果 N 个员工通过一定的分组方式可能会一共需要 K 场比赛,则输出 "YES", 否则输出 "NO", 每组数据占一行。
+ e+ V+ B, I% i, Q; t1 F# v; K X; W' d8 R. s: b+ t
所有的输入输出均为标准输入输出。 * ^/ ]$ F4 V3 U1 O- n1 R& E
" X5 d3 s. l4 n2 U6 j0 D0 d
例子
& I Q, _& |1 V+ l
- ^# ^8 ~+ y3 W5 r4 {6 O9 P# i输入样例
7 ~ |+ Z; Y9 x5 R5 ?
1 }* a5 \- {% Y7 {/ M0 f4 V2 0 & ]+ y2 E5 M$ x j3 M* H, h
( X3 m# Q7 U; g8 C
2 1 , |' F M( T9 M5 M/ l! _+ d
6 P4 O/ T# v# N% L
3 1
5 ~* w" T4 |# w+ e! L5 ^, R9 u! i
( b) I0 D4 p& i0 {3 2 5 a( ~4 `/ q+ }# D- E
5 A2 T$ A7 o: R1 x; d9 @* @
! ^/ S- D, U5 [# Y ^3 d输出样例 ; ^6 H8 w1 H! _* V# K4 H8 a
$ j8 R$ Q7 S# E9 V v
YES 1 B% O3 v! h4 P% e P( m
; g" ~4 @+ C- H0 s+ x) N* p0 ^
YES % S$ {! S) g9 n# H/ p, c+ w
+ a: I4 X1 R8 y3 R% iNO
1 _& w9 b6 {& ^3 d* y) t) |
/ N" ` @ j1 e2 ~$ p; k6 VYES & t( f* f+ I3 S
example1: * v1 Z! a3 n m
#include <cstdlib>
( O- H" j6 ~; x. ]#include <iostream>
$ j, n! H, J, m; p#include <fstream>- x5 [8 V' H. j7 ^
#include <cmath>
" h" U; l3 H/ A6 d) m' u: Ousing namespace std;2 p& C$ i5 i* N3 t
7 c* ~- A5 H2 E6 j2 M: r, B$ s2 G/ u, a$ B2 ^. s0 b8 h! z1 V6 n
bool bt(int N,int K,int min,int count)% v( O) q! J @) v/ h
{
1 ~7 w* U" U/ {6 X# ]/ D //cout<<N<<"|"<<min<<"|"<<count<<endl;$ b! E' F' E+ H
for(int i=min;i<=(N+1)/2;i++)//zhu1 i
{$ L6 T2 l2 g0 t+ q {
3 Y+ C. x& k7 v9 } int tmpc=count;
6 q. f' L- f5 j for(int j=0;j<i;j++)
1 x s2 L; J) P8 H! D8 r tmpc+=N-i;5 B D7 a1 G% [% t6 M5 v) r
if(tmpc==K)return true;7 _2 Y! ]! P U" k
//zhu2 N-i' G/ }! T; @2 z7 V; n- Y
if(bt(N-i,K,i,tmpc))return true;
# c# l( N4 Y! H: }: X }
2 S: a2 b* R; g/ x3 c return false;
4 {8 \" q, q- Q$ z/ o# E9 c }
: E( P- \! T# N# g: {2 tint main(int argc, char *argv[])
0 v% k# n; U* w$ ]5 I" d{
1 ^; n @4 E: k; g! O/ J" P2 P //ifstream inf("input.txt");
% d( G1 W' ]$ t6 s0 Q$ S string str;
; q! w( E$ H- e0 @0 h+ m, `' A- ^ int N,K;, P! j$ U+ {' G) Y$ ~
int count;
7 f o- `- p4 b6 K/ o //getline(inf,str);
/ Q/ |% K6 L- I, u getline(cin,str);, y6 Q3 D2 V* W, y+ d
sscanf(str.c_str(),"%d %d",&N,&K);
2 T7 T* ?2 y* F if(bt(N,K,1,0))cout<<"YES"<<endl;
6 t& m( g# _5 m7 y9 ` else cout<<"NO"<<endl;
4 p6 r# G$ p8 e* Q system("PAUSE");( N3 S3 ^! w8 O" D# P
return EXIT_SUCCESS;
" C7 Y9 s- r: Z4 j, ]}
! @. }8 W5 `9 M& u7 uexample2: //============================================================================
! m4 J3 f0 W3 y C4 y// Name : 1.cpp+ k, k9 m' e# A$ Q* c2 Q
// Author : Xusen Yin
7 T) y" c3 ~( c+ M// Version :" Q( I) w$ e: t V1 p
// Copyright : Your copyright notice
, t8 I/ b8 i z; j$ @; P3 ]// Description : **的规则+ R( R1 C+ J/ ^4 o; L8 ~. i0 V5 n; u
//=========================================================================! ], A3 v+ C4 W* `; J, z
#include <iostream>( d" k5 b/ n9 i0 o6 M& `
#include <bitset>
! U+ T/ t, g) c+ }2 `using namespace std;
( t+ o: f) n$ P% g ^5 S5 q#define MAX 128
, f9 Q( Z% q. B0 m: ~/ z4 e- rint main(){5 s8 }% ^) W% C% Y
int n = 0,k = 0;
* f6 V Z" G; n4 G bitset<MAX> bAssert;
1 _: `& V- ^* a cout << "请输入 N K (以 -1 , -1结束):" << endl;, ] ?0 k7 ~: r( a
size_t j = 0;0 p w! m2 [& ^* A9 G3 b
while(1){
0 J3 v" @# g/ C% K" A$ i cin >> n >> k;
$ ]4 c) j4 B. b5 K1 t, C' X& Q if(n == -1 || k == -1)
4 S, @7 c5 N4 `4 ^1 L break;
O+ l ?1 x0 \9 v- u S" x: p for(int i = 0 ; i <= n/2 ; i++)
: M5 C3 S2 S9 U8 Z if(i * (n - i) == k){" e- J+ c; G, p. S
//是OK的9 k" J- H: x& B J
bAssert.set(j);
; W: ]6 @/ u% I3 i, B break;8 G/ p. B' ?$ ^, c2 u. z U
}! [, Z1 f& i, ~+ w& c0 ~/ R/ ?' g) J
j++;
0 q$ h! f: e/ M+ d7 u/ I0 V s6 g }( y1 N3 i; i$ l2 x. w! ~
for(size_t i = 0 ; i <= bAssert.count() ; i++){
8 e2 [3 F {& D l5 e if(bAssert.test(i))( X8 f7 ?1 j( ~9 x: v
cout << "YES" << endl;
! ^8 Z* {0 E, ?* k else' ~8 w8 k1 O1 P
cout << "NO" <<endl;2 e+ U1 q8 U* ?* T& Z
}( r# O$ x7 ^- B& |7 H% h- ~- w
return 0;
; O* L( |$ d9 N% x* p+ J5 R}& R7 B& C) s2 v: V3 p
6 U4 x$ f! r J$ B$ \example3:( a' e& F/ r# ^7 O. [7 a3 J
import java.io.IOException;) d$ v% }$ `7 @$ k7 c/ D
import java.util.Random;
. S6 X, f8 X! ?2 h: y5 |9 e; y! V* d5 J
public class BtRaceRule
. o; L: G$ `% e; f+ h+ D! f7 Y% [: u k{
* F0 G$ G# J+ P6 q8 H private static int p_number;//人数
% l" j7 R2 S$ c0 c7 j4 N private static int r_number;// 比赛场数
7 F7 c$ o! @4 K: |; n( e public static void logic(int n,int m)
+ A T1 J1 m$ T, t% V% Q O {
2 \$ S2 _8 v( }: p( p4 c int flag = 0;' {7 r% H3 u+ F% n5 D$ ?
for(int i=0;i<=n/2;i++)* G4 C1 t! z+ n0 S
{& Y! O$ T+ \; |* Z# T
int j = n-i;
& Y3 [# [6 F4 V if(i*j==m)
7 N' ^) r I6 ~- k- o" b$ W7 p" R {2 X$ M/ v4 O; L7 E; ^; Q% i; y; m5 y
flag = 1;
1 m9 ?* ?2 B3 s: A5 I' [' H }
# w2 P' l/ a% Z }
4 ?6 H1 N" s/ r. l G if(flag==1)
/ q6 V! f2 g0 \6 m {
5 K2 b7 w% F: u3 ~: q& _ System.out.println("Yes");* e) I5 D: I9 a% E6 @5 {
}
]% j; \' ]" g- a$ m2 G else
' b; x7 s/ T2 F {1 w4 Z9 Z0 P, j+ R' l! |' i$ `9 Z
System.out.println("No");. X e4 G& z2 l2 `; ~4 T% T" z
}
) |6 M u! U F- { }1 y& k( [/ b0 S/ P1 M @
public static void main(String[] args) throws IOException
* Z! u7 f p# W" j) a3 m+ Y {3 t/ E2 v7 b- m2 N# L+ a! n# {
BtRaceRule[] rule = new BtRaceRule[10];
% K3 a$ W: o+ j5 _ GetData data = new GetData();
9 q& q# R P" h) a5 N: A0 u+ @ System.out.println("输入比赛人数和可能的比赛场数:");2 \' G$ \' `+ `8 B( X. r
Random r = new Random();" t' l8 q! c& ~
for(int i=0;i<rule.length;i++); z) m) R" p4 f! E) w/ E
{, k& d! A, a3 k/ p# k1 p
rule.p_number=Math.abs(data.integer()); 7 S# v6 J8 ?& J) M0 U5 e$ f
- n$ E4 I( Q/ `& O/ d rule.r_number=Math.abs(data.integer());' v1 ^1 ~; t" H: V
2 \/ U h+ @7 l2 c0 _. C; K; | System.out.println(rule.p_number+" "+rule.r_number);
A- g* ^; f5 @ //输出一组分组和可能的比赛次数
4 l4 H0 M& a; _0 w logic(rule.p_number,rule.r_number);
; d$ ^+ y- d1 Q' I //逻辑判断,并输出结果 yes or no ! ]4 a( ~1 e+ V0 Z4 K; w; t' ?
} . }% z3 |/ V9 ]+ k; a
}: ]# r& Z: N& N
} |