题目名称:蝈蝈式的记分 ; L" S# _- b4 F. H) B4 Y h4 @/ A
" w5 y" x" X, I0 z& d
内容描述:
: ~9 r8 ~# i* } ]# j9 a8 F8 U" g# C( q' T% w
蝈蝈小朋友刚刚学会了 0-9 这十个数字 , 也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高,于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了,比如用“ 3 2 4 ” 可以表示一方在这一局中连得三分后,输了两分,接着又连得到四分。可是,后来大人们发现蝈蝈只会用 0-9 这十个数字,所以当比赛选手得分超过 9 的时候,他会用一个 X 来表示 10 完成记分。但问题是,当记录为“ X 3 5 ” 的时候,蝈蝈自己也记不起来是一方连续得到十三分后,再输五分;还是先赢十分输三分再赢五分。
9 r4 u& ]+ {$ F
H) l3 @0 {$ k, P( N因为百度内部就要开始进行羽毛球联赛了,要先摸清大家的实力才好分组比赛呢~于是,大人们想知道以前每局的比分是怎样的,以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况,也要输出相应的提示哦。 7 D3 ]) X; x8 o/ e; F
% D- Q* w& Q7 N/ Q) o% m
需要帮蝈蝈进一步说明的是,比赛是五局三胜的,每局先获得二十一分的为胜,但是胜方必须领先对手两分或以上,否则必须继续比赛直到一方超出对手两分为止,比分多的一方获胜。任何一方先获得三局的胜利后就获得胜利,比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。 4 g- K% j7 N# T5 g
, e8 o* A: q% y. ?8 v输入数据:
4 A; r6 @- t/ `/ N" d- L/ B' q) M/ ^( d4 G0 H* r( }$ D
以 point.in 为输入文件,文件中首行只有一个整数 M ,表示蝈蝈记录了多少场比赛的分数。每场比赛用两行记录,第一行是一个整数 N(N<=1000) 表示当前这个记录中有多少个字符,第二行就是具体的 N 个字符表示记录的分数。 ' v7 c* a% d9 V) n" N) v; t: b, S
- M8 f$ t. ?( m9 t/ s* ~输出数据:
+ @% w& O: a9 Z! f" A$ U
) }8 b1 V5 f! H7 _3 {6 Z1 V% H: Y相应的内容将输出到 point.out 文件中,对应每一个分数记录,输出相应的每局分数,每局分数都使用两个整数表示,表示两个选手的得分,中间用 ":" 分隔开;每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候,以” Unknown “一个单词独占一行表示。
; ]% b) \! f8 X7 \' ]9 t' Z: S) y1 D2 N! Y
输入和输出结果数据样例:
% n1 E9 k6 O: ~+ w7 u; j3 Q# ~7 A; Z1 p' Q! s1 ~7 v" D
输入样例
/ G! c1 ^9 ~3 F3 B/ K' g) K. t0 A, m, D) z1 b; y2 \/ X
3
" ~# R' _+ q/ j3 Q" v# q$ O! m$ M. C" r6 g( u( S1 e! q& X
23
" o2 ~0 a# O3 s( |3 \' Q1 l: c" b8 ~ m# z1 R, i: f, O
9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1
- B) x, W3 {3 Z/ C4 W
; X2 C8 A) ]1 c25
$ w( g5 w, m1 O7 E) ]1 F/ ?! h( F( \, T1 r) K8 |. q2 Z) ^0 q5 D
9 3 8 5 4 8 3 9 8 4 X X X X 2 X X X X 2 8 4 9 2 4 ; d3 c8 W i* k$ c9 R9 \
$ o7 {' B" ~ B4 ^# J6 j W- F
43 7 { l6 f6 w. A X9 ^5 \( U
# Y. J# Y7 s/ d/ h* E. D7 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1
' A+ G: {1 l: w y3 X8 Z+ Z * h& O6 W) l" B4 r+ z4 G
. R1 R% D& N$ _% e3 z6 ^( f输出样例
& o: [! r7 f5 G( U1 y
" L3 F, L9 J$ g: z) z21:17
( H% s% Z/ h$ d* l5 h4 F1 y9 a( b7 ~9 T/ t% B- F! y
24:22 , C: c7 }% g: j& m* g
& f) l; F5 x& q
21:3 : Y) q9 p, s2 f' ?1 O
v) i% d3 C1 N. t) x3 {: L, u* E8 W
Unknown
+ m) y9 ]- b) }) v3 L' K9 G8 C7 t* d" l2 S2 A; G1 A. ^0 O1 k4 H
21:14
2 D- p; z2 z4 y# o$ N/ o8 D1 [! ~! L3 ~8 K, A2 K
20:22 + _2 y( [. Y2 \- V" q' C4 f; i
1 ^; a; A+ w2 ]3 I F8 h* Z21:23 7 o& g- g1 D7 V2 i
$ ` ]8 s% e* v6 O! t- [21:16
, {; c- r) a6 Y" j) l: r% p* h5 C% J# N8 r
21:9
; K, g% M9 m* S; e. {" G
: Z1 j# z% Z4 \- W/ a* L5 G& D6 S$ D' b7 A& K
example: public class GouGouShiJiFen {& T% P( f4 R4 A5 r) E2 ?
& V8 @( Z% P, X5 e3 r8 q2 t public int[][] bs = new int[5][2];//当前可能的比赛结果6 n6 X3 E; J+ C9 t
// public int[][] bsOK = new int[5][2];//成功的一种可能比赛结果
; K* G; w( x! s4 {" h// public int[][] bsBak = new int[5][2];//当前可能的比赛结果备份
, |* u8 @$ S) O9 y) T2 d1 M0 e// public boolean hasAOKBS = false;//是否己经有一种可能的比赛结果,如果有多种可能性,那也是Unknown( |1 U% {8 Q) K3 a, D
public int numOfAbleJu = 0; //本行比赛可能的结果有几种0 B- p% T5 Q5 F8 B( |3 q3 N
! x3 N& L. ?( c7 F /**
/ q2 C& S/ N1 R' H3 a * @param index 连续得失分的index! J6 S9 o: I2 L2 J- e# [! R0 g* p
* @param scene 第几局比赛
9 R- h6 g- K4 t; w9 A0 _ * @param whichPlayer index处分为哪个选手得分4 {5 q& o9 f, M; X: j1 n) t! P
* @param record GuoGuo记的一行分
$ J6 }3 O8 F1 T+ B' r * @return 是否是一种可能的比赛结果0 r; }% h: p- b' n2 \* T1 u
*/7 [" C6 a) d) \! J! K7 T; L
public boolean check(int index, int scene, int whichPlayer, int[] record) {2 E s0 M( L0 {& ~. z6 S
int playerIndex = whichPlayer;* G; f6 `; p! l* I# @5 L* n
boolean isWanZhengJu = false;
7 C- b: x/ O8 g5 L, [# O/ P for (int i = index; i < record.length; i++) {
/ U$ V$ t% M7 n s1 O) m/ d isWanZhengJu = false;' r: W! z; ?8 G. M! i
playerIndex = (whichPlayer + i - index) % 2;
: y1 A. o" {: c% K8 T7 m) A, k bs[scene][playerIndex] += record; X- b0 \ t; ^2 ~( v* s* u
if (bs[scene][0] >= 19 && bs[scene][1] >= 19) {//延长球或21:19 必须差二分才算正常结束一局* ]3 ]( W6 d! ^0 [/ V4 h+ V1 e
if (Math.abs(bs[scene][0] - bs[scene][1]) == 2) {//一局正常结束
! k7 k2 }9 ]$ |8 T/ ]/ P scene++;
5 i/ N. ]7 m% ]( c whichPlayer = scene % 2;: j9 @8 A0 L$ k( h
index = i + 1;# R9 P/ g9 Z! B/ L
isWanZhengJu = true;8 z$ v) T) U/ [) b
continue;, N, U" }2 ^, L& C) M
} else if (Math.abs(bs[scene][0] - bs[scene][1]) > 2) {//两者相差大于2球,则错误的
0 x _! ], Y- ? return false;/ U9 L1 o! g' ]- w! m0 @; B3 s
}
/ f5 p& b+ q3 X+ E( K } else if ((bs[scene][0] > 21 && bs[scene][1] <= 19) || (bs[scene][1] > 21 && bs[scene][0] <= 19)) {//一方超过21,一方<=19,是错误的
7 v1 p1 N# _, n return false;
2 g6 ?& {1 a' J- g5 I9 p5 G( j; ~ } else if (bs[scene][0] == 21 || bs[scene][1] == 21) {//一方为21,另一方<=19,一局正常结束
' @0 v" q. y3 ]* X scene++;7 g3 t0 o# v, g. h9 H( m0 H
whichPlayer = scene % 2;
8 S S o+ ~8 v index = i + 1;
& I9 F2 W6 D0 f- q) l5 a isWanZhengJu = true;, m: M) @. h8 A1 {
continue;
8 t! A( T5 G$ F0 A# F0 C- R4 M }( |* V, `6 D/ [" u& _, I
if (record == 10 && i != (record.length - 1)) { //下一个数分情况% G! }( Z# V: K' b( |; u) Q) j
int[][] bsBak = new int[5][2];
; L& y9 o1 i8 S6 U0 U7 c cpy2deepArr(bs, bsBak);, |. o! t; y- g& D% M/ K7 s7 J
if (check(i + 1, scene, playerIndex, record)) {
# a9 p9 @4 B; W cpy2deepArr(bsBak, bs);+ s# Y) ?3 O/ o+ M5 C
if (check(i + 1, scene, (playerIndex + 1) % 2, record)) {//有两种比赛结果,错误0 O5 g" s- a+ R7 D6 v _3 P
return false;) d3 Z; K2 v) @+ l5 u8 \+ u1 Z
}1 e& | k1 k: o. r; N! p4 p
return numOfAbleJu < 2;, `7 }2 ^) `) r3 ]- }; g
} else { J. |! u$ F4 I& B' H/ z5 u$ k
cpy2deepArr(bsBak, bs);
( l# G! S9 Y0 R Q# L! A6 I( A if (check(i + 1, scene, (playerIndex + 1) % 2, record)) {7 [4 l/ L. M% _) O
return numOfAbleJu < 2;/ T+ Q6 ?9 z% ~4 m/ m: c8 s: x
}" D" [! t2 a8 g6 n c5 d8 a; B
}
+ ~1 g. h6 h) e0 g, w return false; Y' Z: z+ G5 c a; A3 d3 s. Q* _
}
8 H( @8 ~6 U* e2 r. f }' |9 o: D( o) q$ x1 K5 G! f
- \ H! V' f, S0 ? if (!isWanZhengJu) {: q- _9 X6 ]8 X; n
return false;. H4 z- e, f' l( N$ C' {& @# r" A2 F
}
7 _- R: `* [+ L( v$ h3 @- y9 a// //检查是否符合五局三胜. d4 K% ?) [; o+ I3 h$ F
// int a = 0, b = 0;0 K. d+ d+ g! v n% `" O! l( E
// for (int i = 0; i < bs.length; i++) {" T8 F7 ~ j1 T8 @
// if (bs[0] == 0 && bs[1] == 0) {//没有局待检查了
! z) Q2 k) k: Q, Q# E0 S8 E. ]// break;( s. _7 g" j7 G0 {
// }& f& Z+ {+ l8 r4 U9 }# o/ k
// if (a == 3 || b == 3) {//己经有人先得三局,但是还有局待检查,不合五局三胜制) Y. |7 S8 O. R. r- Z
// return false;
6 _$ a, f( X9 z' o// }
7 @, b; S, i/ h+ l// if (bs[0] > bs[1]) {
! r. s" M& R+ C- I: Z+ H' r// a++;
; @8 f- `; Q+ b1 g// } else {/ W4 q+ L5 J& h( J& Y1 ?
// b++;
3 k, L& G/ h- \5 G7 `+ j& z// }$ O; q S$ S' ~
// }
9 V5 U: I, ]2 }5 W1 v// if (a < 3 && b < 3) {//没有一个人得三局,故错误4 d0 O9 k% H. y( C$ h) s' b8 f6 a
// return false;1 \9 g2 I6 o$ h+ f. r8 I$ y
// }
' \. ?, b& p$ d. J& o //只要有三局及以上正常结果,则可视为OK1 V1 t1 g3 R- ~. X- n
int count = 0;- V9 d; ?; k4 x% p5 L
for (int i = 0; i < bs.length; i++) {
* G. ?* o" U$ U( u, R: P if (bs[0] == 0 && bs[1] == 0) {//没有局待检查了6 m7 E( i5 s. |# T [6 n3 M
break;
# P2 B8 i$ _) }5 Q( M( A0 d }
9 A3 M5 a; n ?! d8 }8 l) d4 o) S count++;; R1 @* g& K5 o1 l+ s
}
+ Y' w- @5 e# N7 s if (count < 3) {: s5 W) @' ~' N8 n$ ]/ p. I
return false;
& x* x, X h% z }, L+ X7 C1 a* G+ U' L+ o
/ b4 I# k8 M' k0 f" X6 n4 Q) ?" _ numOfAbleJu += 1;
; E- q* o, Z2 r3 z* M return true;' J# I* x+ Z1 B* w( o) g
}0 ?9 B5 d$ X) c( B* r
private void cpy2deepArr(int[][] src, int[][] dest) {8 `% ?$ j5 p; ?8 R
for (int i = 0; i < src.length; i++) {9 V" h3 x% K4 @" H1 a
for (int j = 0; j < src.length; j++) {
( U) j. o3 @1 u. b8 ?8 { dest[j] = src[j];* p) \5 K* p5 t) P! y/ f' f0 J
}
3 [8 F# D6 A8 E i* X/ @ }
7 ^) J) ~, A5 Y- o }' _0 {! t2 n& I, y6 P+ h
" h2 t! b7 [& {* ~2 i" W9 _
public void printNowCheck() {
. p! |+ G3 s7 s% J& E' p i for (int i = 0; i < bs.length; i++) {
6 K; ~9 h# o' i- ~) i& { if (bs[0] == 0 && bs[1] == 0) {//没有局待检查了3 o' ^: Y; n6 O9 n3 w( W
break;5 z7 Y! g6 b! [, ?. w7 W4 q3 O
}' S6 b* Q( v3 H0 m4 s2 ~' L
//因为无法得知两位选手谁赢哪局,故以大比分:小比分输出% m+ H& W0 y ]1 ]. ?
if (bs[0] > bs[1]) {2 Z, E/ J6 X; k: l R2 j
System.out.println(bs[0] + ":" + bs[1]);% q, N; n, k7 U U; r+ e
} else {% h4 s' t9 I7 W Q0 E
System.out.println(bs[1] + ":" + bs[0]);
) I B2 G% I% }$ C }5 c& z) z5 K7 R, u2 F& F1 q( F
}
- R+ ]: r/ o2 ]6 { }0 E5 G7 g2 B0 O3 d! p( z" \
public void resetCheck() {6 N2 T% {6 X \) H8 o
for (int i = 0; i < bs.length; i++) {0 z9 X8 k1 }& Y8 s- t7 ]# Z4 Q* O
bs[0] = 0;# q% O7 z8 a/ z9 h
bs[1] = 0;: ]( K! x1 a" V' H
}2 h; z9 U! \6 m, h4 w" O
}
% T5 h$ T0 t( v" R! @ /**1 }6 u% V c4 c% H& k* q$ n
* @param args
) z& u, _; C7 v% e+ B */' a# X: X# O }7 C& U' W$ Y4 _/ k
public static void main(String[] args) {
% ~8 y/ X: ]5 F& W // TODO Auto-generated method stub. e: D; M4 J: x t$ W
GouGouShiJiFen obj = new GouGouShiJiFen();
9 N) @! C. R0 E, q. e int[][] testData = {$ y, h4 s) A. }
{9, 7, 3, 6, 2, 4, 7, 8, 3, 2, 7, 9, 10, 2, 2, 1, 2, 1, 10, 1, 10, 1, 1},: d/ {! g1 R# `2 u6 S) J: y
{9, 3, 8, 5, 4, 8, 3, 9, 8, 4, 10, 10, 10, 10, 2, 10, 10, 10, 10, 2, 8, 4, 9, 2, 4},
; v- U a) }& G {7, 7, 7, 7, 7, 3, 4, 5, 6, 7, 6, 5, 4, 2, 1, 3, 5, 7, 9, 7, 5, 3, 1, 3, 0, 9, 9, 3, 9, 3, 2, 1, 1, 1, 5, 1, 5, 1, 5, 1, 5, 5, 1}+ S4 |& {" Q$ s- v7 g
};
: C7 |4 Y: I8 f; ] |1 ? for (int i = 0; i < testData.length; i++) {: o; A7 s ?$ x+ K, ~& n, n! t
if (obj.check(0, 0, 0, testData)) {: M9 i) S% P& l6 b: d
obj.printNowCheck();) L4 e# O% p0 C6 e$ H/ t! J
} else {
" X2 v9 M: y; Y) S! E m' ^ System.out.println("Unknown");
, S% y0 N9 p$ c J; Q5 I3 [ }
. r9 {6 R9 \" H9 u8 [6 |" n* ~ obj.resetCheck();& _' `/ L4 Q' a$ a! K; O: c! T B
}" _# T8 {' I- ?+ `8 v i% W
}' A: y: Y$ F( @6 m K! h8 L" P. n
/ v0 C( w6 c# R1 T6 {9 R
} |