题目名称:蝈蝈式的记分
& g2 P; ?8 U& o/ C i6 O) |4 H6 e- p7 e8 Y( s/ _0 z1 C& t' j
内容描述: 8 \, s ^' U! C" r' J# ?; e
; s& J: G, U- \* U( Y/ d' W* h蝈蝈小朋友刚刚学会了 0-9 这十个数字 , 也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高,于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了,比如用“ 3 2 4 ” 可以表示一方在这一局中连得三分后,输了两分,接着又连得到四分。可是,后来大人们发现蝈蝈只会用 0-9 这十个数字,所以当比赛选手得分超过 9 的时候,他会用一个 X 来表示 10 完成记分。但问题是,当记录为“ X 3 5 ” 的时候,蝈蝈自己也记不起来是一方连续得到十三分后,再输五分;还是先赢十分输三分再赢五分。
+ q5 J* K8 _+ g, R( X
3 h, ^/ ]; i( p) N4 d) F7 H因为百度内部就要开始进行羽毛球联赛了,要先摸清大家的实力才好分组比赛呢~于是,大人们想知道以前每局的比分是怎样的,以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况,也要输出相应的提示哦。
" c! d8 q# O- y, k7 _4 m% v; O- q% U) _4 X; D2 s) E, T
需要帮蝈蝈进一步说明的是,比赛是五局三胜的,每局先获得二十一分的为胜,但是胜方必须领先对手两分或以上,否则必须继续比赛直到一方超出对手两分为止,比分多的一方获胜。任何一方先获得三局的胜利后就获得胜利,比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。 % @3 Y0 `$ B# D( Y4 G* x
# G$ q. O/ T3 q' B7 r: L/ k, t, u输入数据:
3 {. @3 z# Q) l i. l4 o4 } y, q6 ~+ y7 [# k* y) O0 t" M! v
以 point.in 为输入文件,文件中首行只有一个整数 M ,表示蝈蝈记录了多少场比赛的分数。每场比赛用两行记录,第一行是一个整数 N(N<=1000) 表示当前这个记录中有多少个字符,第二行就是具体的 N 个字符表示记录的分数。 4 L1 J- n0 s3 i+ [
+ e8 Q+ v5 B+ ], {! m
输出数据: 4 N- F" s& d; x `0 Y; C
3 }: q% V& @( J
相应的内容将输出到 point.out 文件中,对应每一个分数记录,输出相应的每局分数,每局分数都使用两个整数表示,表示两个选手的得分,中间用 ":" 分隔开;每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候,以” Unknown “一个单词独占一行表示。 6 m6 U5 C% a, f2 P7 y
; V3 B- x; Y0 S" p
输入和输出结果数据样例:
4 f4 _9 ^- J1 p. M- w( |6 C
- D, p8 a9 r% W输入样例 * u! J, m e0 ]: w4 J' X9 P: z9 N
, M" o; }8 r4 Q4 Z
3 8 @7 y3 _( U. L" h
, n3 t9 f3 d0 z7 t
23
6 W8 s ^$ d# j" i* k4 `# o9 \7 ~" {( U/ p( [7 T4 A
9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1
) T1 m1 `6 Q4 A" l2 H; d
6 e, c4 l; K7 [. ?25 . P H! b- P: b8 Q e
0 {5 i) f0 z5 G }1 } Z
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 * K5 _2 z2 p' t% @
9 s0 c. ~+ R( s" ]+ M5 k43 $ p9 [0 V7 k+ X- \% g) F5 X
% B7 F$ Z" X3 Z+ e o
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 / j2 ?: T7 w4 Y8 Y3 ]
) I, Z$ D0 c% f6 L9 f
1 v; P3 m" l* k: L/ L
输出样例 ) Q' v" ~- G- x1 N& n. X8 m% s( ?
' |: U4 T$ q& E% R9 P k6 I21:17
; Z+ a( ]2 N1 R& p. ~. I6 v! f6 s4 e5 d7 K, p1 Z
24:22
1 O- R* a6 `4 L% e; g' ~' g* j+ f0 y- f( P( z! q
21:3
6 P8 e( y1 u _ K
: s9 I' E/ b7 _7 U2 F0 A% S o+ BUnknown y$ m/ x. d4 ^0 h
. S7 P* r3 ]: X0 q! ]- F% C' J
21:14
, W/ c" W+ O) V( G% v+ u' v% F% D4 G3 x3 A
20:22 ' {8 D! K7 x6 {/ X% N2 l
% z ^9 X2 t! F+ ]0 O& K" v$ g
21:23
$ Y) J: U+ b( z' d- v3 P3 q
: ^6 }* {- K1 s; O/ X2 S21:16
; W( t- C! A& d( H1 R q
' E- O- {8 `* z$ @21:9 & |4 i( f2 N4 D( h0 A
' J& B" g" ]. E! l0 t8 w; g
/ v2 Z% K$ i2 W* b+ }7 L
example: public class GouGouShiJiFen {
" H5 Z1 M; W1 t1 B2 }. D; h) b! A
) c1 A0 V: X& O( V; W$ b2 X) ^+ w public int[][] bs = new int[5][2];//当前可能的比赛结果
6 x! V/ I, u; V7 _+ m' D3 _% I// public int[][] bsOK = new int[5][2];//成功的一种可能比赛结果
7 ^5 M$ G* f# f// public int[][] bsBak = new int[5][2];//当前可能的比赛结果备份+ d% E/ N5 o9 ]0 q8 d
// public boolean hasAOKBS = false;//是否己经有一种可能的比赛结果,如果有多种可能性,那也是Unknown4 b2 m1 |8 i" S7 ^8 P; f& ^
public int numOfAbleJu = 0; //本行比赛可能的结果有几种
3 Q9 J' Y4 t: T+ U" n" H
, @. m+ J2 M8 e% h- J$ J /**
4 E) U8 l+ N9 Z9 F7 d5 W: H * @param index 连续得失分的index
* I0 b) c. t: m0 ?3 r! i5 Z * @param scene 第几局比赛 M, z& D8 b5 O1 _, ^
* @param whichPlayer index处分为哪个选手得分: g0 G( F; j/ O2 A4 x$ }
* @param record GuoGuo记的一行分
# i- z: G" ?0 J" [6 `7 I * @return 是否是一种可能的比赛结果, ?: M% y* Y0 {$ t3 u
*/: J" m' n t/ l8 \( F* S
public boolean check(int index, int scene, int whichPlayer, int[] record) {
" i( W0 L1 w8 U6 {2 I7 ^ int playerIndex = whichPlayer;
9 ], S; [% S# i# t1 \- I boolean isWanZhengJu = false;" W, z- B8 t3 O5 A# u3 o' u
for (int i = index; i < record.length; i++) {- n& ]+ b8 P' c5 e- r6 g
isWanZhengJu = false;, U# ^9 f" H+ a4 k% `
playerIndex = (whichPlayer + i - index) % 2;. L0 D8 \" O/ I+ D' K
bs[scene][playerIndex] += record;
! q, Q& t7 R0 Y# L# o+ W if (bs[scene][0] >= 19 && bs[scene][1] >= 19) {//延长球或21:19 必须差二分才算正常结束一局9 c$ B3 D8 I# }$ C2 B$ y
if (Math.abs(bs[scene][0] - bs[scene][1]) == 2) {//一局正常结束! u; E6 Q, z! f& _$ f1 i& I" w* k( Y
scene++;
+ R8 {6 k; F* T/ c" d whichPlayer = scene % 2;) [9 V: S4 x+ ~- C, H
index = i + 1;) [6 U. f- j$ c
isWanZhengJu = true;6 X2 k) J/ h- m! T0 a/ Y
continue;* p, F! h! l2 F( N2 N; O+ f
} else if (Math.abs(bs[scene][0] - bs[scene][1]) > 2) {//两者相差大于2球,则错误的
' R' `% F: k! L: ^6 `7 f return false;7 |4 U/ @, l2 p' I) j# D
}
$ [$ |! Y+ d1 m0 ]8 Z7 ?; j7 z } else if ((bs[scene][0] > 21 && bs[scene][1] <= 19) || (bs[scene][1] > 21 && bs[scene][0] <= 19)) {//一方超过21,一方<=19,是错误的 Q+ ~. G4 T9 d2 R C1 @, Y
return false;. g/ ^* E+ t( M+ v
} else if (bs[scene][0] == 21 || bs[scene][1] == 21) {//一方为21,另一方<=19,一局正常结束5 E% j+ z3 x' a2 K9 L* @
scene++;, j/ d1 J9 x; \: l# W
whichPlayer = scene % 2; g' r( R1 e F7 [9 |+ f1 B
index = i + 1;
# w2 A6 ~7 p4 B' _: q' ~ isWanZhengJu = true; ~/ o% |6 h# |7 @& o+ k8 @: W
continue;
( R; n8 Z4 U* ?: H0 k2 l }
1 V C3 z" \7 J( @* N if (record == 10 && i != (record.length - 1)) { //下一个数分情况% @. G! u8 Q7 s; Q# Q1 }4 I
int[][] bsBak = new int[5][2];. g- e3 m7 V( W4 ^
cpy2deepArr(bs, bsBak);
' A/ S8 a0 r4 e7 A if (check(i + 1, scene, playerIndex, record)) {( P% H: x9 u5 \! o1 M3 |. e
cpy2deepArr(bsBak, bs);6 @" h9 Z) G7 i( N J
if (check(i + 1, scene, (playerIndex + 1) % 2, record)) {//有两种比赛结果,错误
) F3 E8 v8 k0 m; j% D return false;
* Q( ^) A# @1 T+ O0 S2 { }3 E, M3 O- A, B" H
return numOfAbleJu < 2;' K) J: R- [$ U0 @9 c
} else {
2 K; A+ Q; h, s3 V cpy2deepArr(bsBak, bs);2 A, X8 y1 r8 U2 k* H
if (check(i + 1, scene, (playerIndex + 1) % 2, record)) {7 p7 v d8 k% `7 Q" T a
return numOfAbleJu < 2;' Y! t% v! `5 N; K% ~ Y( [
}3 b* c. ^4 H9 G. i
}
+ |; R. r1 Q9 I/ s( P return false;
' c5 E0 Y) g/ w2 O }
0 U1 E! z! S* ~; ?! @; m }1 Z4 e" v5 a* W* T
1 v6 `4 P, S) p0 Z% f2 x4 o$ ]) i if (!isWanZhengJu) {3 c1 U. |+ A }7 t
return false;
7 p4 E( |# F5 L }
$ f- |1 a9 k9 H5 K$ X+ t% Z// //检查是否符合五局三胜7 s* t6 G! m. u# Q# H7 a: Y
// int a = 0, b = 0;
! s% C# C1 E! B) L" q7 k// for (int i = 0; i < bs.length; i++) {( t4 e, }2 f5 d
// if (bs[0] == 0 && bs[1] == 0) {//没有局待检查了+ W- x" O$ ]) ]' a! x# b- {' @, }
// break;
# _. |2 u( b8 N4 I1 Z2 h; |5 x9 M. X// }: }9 b4 { W# g5 |5 B
// if (a == 3 || b == 3) {//己经有人先得三局,但是还有局待检查,不合五局三胜制" g. M- x; }( x; {0 A" D! H+ n
// return false;
# s. ?3 V5 |2 K, R, X2 U! A- T// }
5 s$ Q! f6 A0 a8 O# ~// if (bs[0] > bs[1]) {
8 g3 \# G: C/ y5 Y. M1 \// a++;) _' [2 F3 Y A' u
// } else {0 O8 ]8 _2 H0 M4 w2 i) a
// b++;
) }: l5 X9 c: S! \+ M// }8 ]8 [- x# z0 e6 h
// }
4 h% V( g% M- ]5 ^, Q// if (a < 3 && b < 3) {//没有一个人得三局,故错误0 v" D1 h: t! G3 e# f0 V! P/ c) J9 g
// return false;
4 `" _) t, J! M$ Q) \// }
( t- o7 V6 s: G. `2 b7 P //只要有三局及以上正常结果,则可视为OK5 _9 q8 ?+ y( c7 ]/ n7 O) w8 f% }+ s
int count = 0;
5 _' j( C! T0 t& q2 v4 M4 c for (int i = 0; i < bs.length; i++) {
6 H3 X3 B0 ~. h( d# l8 ? if (bs[0] == 0 && bs[1] == 0) {//没有局待检查了
; e1 V. n# A1 Y break;
* R! K0 z2 V. n1 z4 y }
- ^6 z2 M' X& m6 r* v count++;
% U; i' E5 g7 a, I( v; J }
' y" ~: O" X* |2 r1 V" W( { v4 C if (count < 3) {
( k. t- n6 y% Q1 I return false;- J& j A1 o* E6 x" n# R5 u
}! ?# ]' R+ }) Q, C8 v- j" m
% T: y; p3 T9 R6 G" d9 |8 b' M& V
numOfAbleJu += 1;0 f/ z6 T- m( p* y4 X* X$ F
return true;
( g: D5 A/ S) ]% ^& @' [ }
* J7 N+ K+ _# F9 w, L* _4 u6 ^" S private void cpy2deepArr(int[][] src, int[][] dest) {3 ~% b; W" a6 J3 q) c8 Q
for (int i = 0; i < src.length; i++) {
0 _; _8 R$ d3 g0 E, K for (int j = 0; j < src.length; j++) {
. i" W4 B1 O" ]' k" m% q dest[j] = src[j];
, V% X$ H F q }
7 c0 Z7 d& C8 T. v4 i }
- |; a( y2 E* f# d* |+ X }" l/ T! H$ N2 z y
" I+ ?" K1 G7 P3 m
public void printNowCheck() {
8 M. p% h2 O# P" j1 E7 u for (int i = 0; i < bs.length; i++) {
, n7 g- t# a$ N. |7 ? if (bs[0] == 0 && bs[1] == 0) {//没有局待检查了
- \+ |) x1 U; y6 V' S6 Y9 H break;
- S5 ]/ R: L1 r }
- h. q! Y5 A' S" m5 G. d: ] //因为无法得知两位选手谁赢哪局,故以大比分:小比分输出# f X# J& W0 O [
if (bs[0] > bs[1]) {( T, \( w# t9 y# k
System.out.println(bs[0] + ":" + bs[1]);
! N$ u1 ^6 a9 Z5 F } else {! }2 ]( b6 E9 ]. R* x n
System.out.println(bs[1] + ":" + bs[0]);# `" ]' R* F0 ?- @! ?7 I
}
- R4 f$ e3 f# d. c2 x% E& `% j. f1 l3 r }; u5 T9 I6 Y/ X
}3 v5 x: Q$ A }9 Y/ P' R6 [
public void resetCheck() {( g3 G+ J& W$ _" O( _
for (int i = 0; i < bs.length; i++) {1 d4 _, L l7 a) n- ^6 D0 s
bs[0] = 0;3 j0 R' {: K0 o# `, z3 _0 X# `% m+ L$ S
bs[1] = 0;$ ^- H2 u/ u+ S2 _3 l
}
3 h5 ? j0 M, o9 \7 B }
9 c9 x: |4 x4 z0 d+ {' m1 { /** J$ P I! [, |) p1 x$ E/ m
* @param args
6 _+ n% R0 c8 r7 S7 \ */
3 C" [! N: h; G3 o4 @6 F9 z% L public static void main(String[] args) {
+ ]" T Y* D2 |/ P" {; A& a0 W // TODO Auto-generated method stub- h k# d. ?. S
GouGouShiJiFen obj = new GouGouShiJiFen();
4 M+ |( ^, K9 t& R int[][] testData = {
; F! L4 k2 _; R3 g; q1 L9 s {9, 7, 3, 6, 2, 4, 7, 8, 3, 2, 7, 9, 10, 2, 2, 1, 2, 1, 10, 1, 10, 1, 1},$ c1 s" H; F6 C n
{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# Z' ] G" e {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}
8 z6 Q4 k' n! l* H8 @) k7 x2 Z };
$ k3 u8 O8 Y% D. N8 O# ^ for (int i = 0; i < testData.length; i++) {2 j9 H7 T, E2 U X1 s% j7 P2 f# @
if (obj.check(0, 0, 0, testData)) {. w0 x T( i7 _# R' X& V* S
obj.printNowCheck();
0 S; N- a! L) {: B& k } else {9 |* Y& `* Y: `' }3 m6 N5 H1 c4 W1 M4 p
System.out.println("Unknown");
7 P$ a9 q; x1 b1 I2 ^ }* v1 a1 E$ Y. M# s
obj.resetCheck();
5 y! o+ _! Y I* F+ r. M }9 U4 C: G7 V! t6 u, ] N9 x1 H
}
( m/ Q4 h, S# N: `2 E% \+ ^, O4 a" X9 O& V1 w% i
} |