162 - Beggar My Neighbour

[wyvmak]

pls help. i think i don't understand how it works.

say 52 cards, input: c1,c2... c52
then non-dealer gets c51, c49, ... c1.
and dealer gets c52, c50, ... c2.
then non-dealer starts with c51, dealer starts to play with c52. so on.

let's do it by example (simplified):
non-dealer (3 cards): 2 J 2 3
dealer (3 cards): 2 3 4 5
so 2->2->J, then dealer needs to cover by 3.
so will become
non-dealer: 2 3
dealer: 4 5 2 2 J 3,
is it? and the dealer next plays 4?

that's my interpretation, and i don't know why i can't even product the sample output "1 44" from the sample input.

[Even]

think about this situation...

no-dealer : 2 Q 4 3...
dealer : 3 K 5 2 ...

then begin ...

2 -> 3 -> Q ...and now dealer should put 2 cards...
but when dealer put one card...we find it is "K"...
then dealer need not put the second card...
and no-dealer then should put three cards....

till any player has no cards to put...
and the other will win the game...

[wyvmak]

i understand that. it'll be reversed when 'K' is put. but still cannot work out the sample. so what else is missing?

[Even]

Sorry....I made a mistake..

if ...

non-dealer 2 J 2 3
dealer 2 3 2 4

than 2-> 2-> J ...then dealer cover by 3 ..
and then "non-dealer" take the heap...

non-dealer 2 3 2 2 J 3
dealer 2 4

then non-dealer put 2 ...

[wyvmak]

oh dear, poor my english and understanding, thanks a thousand

[Aggag]

Does anyone have some sample inputs for the "Beggar My Neighbour" problem (162). I have got the provided sample input right but still get WA from the judge over and over again. Its may be that i am missing something that isnt included in the sample input. Thanx alot in advance.

[Observer]

Hello!!!!

Plz anyone plz help!!! I'm getting WA!!!!
My code can pass the sample input, and I can't think of any cases that make it fail......

Plz could someone give me some test cases??? Thx in advance!!!!

(Hope someone can give me a reply)

By the way, what should be the output for the following case?
H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3
H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3
H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3
H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3 H3
#

[Observer]

FInally got an ACC!!! I've made a very very minor glitch......

Btw, the output for the case above is '1 0'.

P.S. My program fails in cases like this:
DQ H2 H4 D4 D5 HK D3 D4 H3 D5 D7 S3 S2
D2 H2 H4 D3 D5 H6 D3 D4 H3 D5 D7 S3 S2
D2 H2 H4 D3 D5 H6 D3 D4 H3 D5 D7 S3 S2
D2 H2 H4 D3 D5 H6 D3 D4 H3 D5 D7 ST S2
#
The Output should be '2 51'......

[parmaia2000]

Please, im looking for some test cases that can help me solve the problem, i test my code with all the cases listed here and i get the correct answer but i still get an WA.



PD. Sorry, my english is not the best, but i do what i can!!!

[Krzysztof Duleba]

I can't understand why I get WA. Are there any special cases I should care for? Any sample tests? Which input format is correct:

A)
HA H3 H4 CA SK S5 C5 S6 C4 D5 H7 HJ HQ
D4 D7 SJ DT H6 S9 CT HK C8 C9 D6 CJ C6
S8 D8 C2 S2 S3 C7 H5 DJ S4 DQ DK D9 D3
H9 DA SA CK CQ C3 HT SQ H8 S7 ST H2 D2
HA H3 H4 CA SK S5 C5 S6 C4 D5 H7 HJ HQ
D4 D7 SJ DT H6 S9 CT HK C8 C9 D6 CJ C6
S8 D8 C2 S2 S3 C7 H5 DJ S4 DQ DK D9 D3
H9 DA SA CK CQ C3 HT SQ H8 S7 ST H2 D2
#

B)
HA H3 H4 CA SK S5 C5 S6 C4 D5 H7 HJ HQ
D4 D7 SJ DT H6 S9 CT HK C8 C9 D6 CJ C6
S8 D8 C2 S2 S3 C7 H5 DJ S4 DQ DK D9 D3
H9 DA SA CK CQ C3 HT SQ H8 S7 ST H2 D2

HA H3 H4 CA SK S5 C5 S6 C4 D5 H7 HJ HQ
D4 D7 SJ DT H6 S9 CT HK C8 C9 D6 CJ C6
S8 D8 C2 S2 S3 C7 H5 DJ S4 DQ DK D9 D3
H9 DA SA CK CQ C3 HT SQ H8 S7 ST H2 D2
#

[Krzysztof Duleba]

It came out that I misunderstood the problem. A player looses not when he has no cards, but when he has no cards _and_ he has to make a move.

[Farid Ahmadov]

Hi. Need some %100 I/O to test my program.
Thanks in advance.

[El-idioto]

My TLE app can solve about 250000 inputs in 10 seconds on my Athlon 2200. I can scarcely believe my app is too slow.
Unfortunately, it is possible to have a cycle in the game. One such a cycle is:

Code: Select all

ST S8 C6 C6 ST HT D6 D6 DK H2 D6 D5 D2 
H3 C8 H8 D5 H3 HT CJ S5 D2 H7 H7 SK ST 
D3 D9 H3 S9 C3 CT C6 S8 S7 H5 H5 S3 ST 
C7 H2 H2 D6 D5 H5 D8 C8 C5 D4 H3 S8 D9 
#

Can someone with an AC app tell me whether their app gives a result?

Also, can someone with an AC app send me their (Windows) exe so I can test against my app?

[danielrocha]

I don't think you should really worry about that input. I ran it on my AC program and it also locked (circular loop). There were two inputs that I tried before getting the program accepted:

Code: Select all

H9 DA SA CK CQ C3 HT SQ H8 S7 ST H2 D2
S8 D8 C2 S2 S3 C7 H5 DJ S4 DQ DK D9 D3
D4 D7 SJ DT H6 S9 CT HK C8 C9 D6 CJ C6
HA H3 H4 CA SK S5 C5 S6 C4 D5 H7 HJ HQ

DA SA CK CQ C3 HT SQ H8 S7 ST H2 D2 DQ
S8 D8 C2 S2 S3 C7 H5 DJ S4 H9 DK D9 D3
D4 D7 SJ DT H6 S9 CT HK C8 C9 D6 CJ C6
HA H3 H4 CA SK S5 C5 S6 C4 D5 H7 HJ HQ

#

The output:

Code: Select all

1 51
1 41

[shuniu]

I get WA for this prob, can somebody help me out by posting an AC output to the following input? Thanks!

Input (30 randomly generated test cases):

Code: Select all

S8 D8 HQ S6 HK C8 HT D4 H2 H7 SA D5 D3 
CK H5 H4 C4 D6 S2 DA ST C6 D9 D2 DQ SQ 
S4 DJ CA C2 H9 C5 HA DK CJ H3 S9 C3 HJ 
SK CT CQ SJ C9 DT S7 S5 H8 S3 C7 D7 H6 
C3 DQ CJ C6 SK DK S8 D2 CT HT DJ S9 S4 
D6 S5 H2 HJ S2 S7 DA CK D4 ST CQ S6 C9 
SQ D3 HA SA H4 C7 H5 H8 D8 H9 H6 D9 CA 
DT H7 H3 HK C8 SJ C5 D7 C2 S3 D5 C4 HQ 
CK D7 C9 D2 HQ HT SA D6 DT C5 CT S3 HK 
S4 C2 C7 HJ D9 CQ H7 H5 CA DQ SK S6 S8 
C3 H3 C4 C6 H6 DK H9 HA D4 CJ H8 S5 DJ 
SQ S7 DA ST D8 S2 D3 S9 D5 SJ H2 H4 C8 
H9 S7 HQ H6 C8 DA H3 SJ DQ ST H5 H7 C7 
H4 HA D5 HK D2 H2 HJ CK S5 CA D9 C6 D8 
CT DJ SA DK S9 S6 S4 SQ C4 D6 S2 D3 D7 
S8 SK CJ H8 DT D4 C5 CQ C3 C2 S3 C9 HT 
DJ H4 H5 C3 SA D5 C4 SQ H3 C9 S5 H7 S6 
DQ S7 CT S9 C5 HK S3 C2 DT H9 HQ CQ D8 
H2 D4 C7 D9 D7 DK CA DA SK ST SJ C6 CK 
C8 H6 HJ HA D3 D2 S2 H8 CJ S8 S4 HT D6 
C9 C3 C4 D7 D5 S9 S2 H2 S3 HQ H9 DJ SJ 
HA C6 S4 CQ H5 S6 C8 S7 H6 CJ DQ ST CK 
D2 S8 DK CT SK C2 S5 D8 H4 HT SQ CA D3 
D4 SA C5 HK D9 HJ H8 DA C7 H3 DT H7 D6 
D5 ST CJ H7 C2 DT D6 HQ HJ D3 SA DQ C8 
D8 DA D4 SQ CK HK HT H2 SK H5 S7 H9 HA 
H8 H3 C3 D7 S4 CT CA S2 S9 SJ C9 S8 S3 
D9 C5 DJ H6 C4 C6 DK C7 D2 S6 S5 H4 CQ 
HA D8 H5 DQ D5 C6 HT ST DT H8 HQ C3 CK 
DJ HK SA H7 D9 S3 S5 H2 D7 C9 S4 S9 C2 
S7 H3 D3 C8 SK C4 CJ SQ H9 C5 CQ D6 DA 
D2 H6 DK C7 D4 CT S2 H4 HJ S6 SJ S8 CA 
C2 SQ CQ SA CJ DQ H9 DK H5 D4 CT S3 H3 
HT C9 S5 D9 D2 D7 S9 S4 C6 S8 HA CK D8 
D3 S2 H6 C7 C4 D5 C5 D6 SJ HQ CA H4 C8 
HJ SK DJ DA S7 ST S6 H7 DT HK H2 C3 H8 
D6 D7 S2 S3 D5 CQ DK S6 CK S9 CA D9 SA 
C8 S8 HJ H2 ST H9 C4 D8 DQ SK S4 DJ SQ 
HA H6 D4 H7 H5 C7 SJ HT H3 C5 S5 HK HQ 
D2 DT D3 C9 C3 DA CT S7 CJ C2 C6 H8 H4 
C2 C5 SK DJ C4 H2 D9 S5 S2 D4 C6 DQ H3 
CT SA H9 HQ S8 S4 H7 D2 H4 S3 DA H8 HA 
HJ H6 CK D7 CQ SJ SQ DK D3 D8 C8 DT HT 
C9 H5 D6 HK CJ S9 S6 ST C7 S7 D5 C3 CA 
S9 DQ D5 S6 S7 D6 C7 D4 S8 SA HJ S2 ST 
D3 DJ C4 H8 C2 HT C6 HQ S3 HA SK SJ D2 
SQ S4 DK CJ D7 CA S5 H6 D8 DA CQ H3 H2 
H9 C9 H7 H5 C5 D9 DT CK HK C8 C3 CT H4 
D3 C7 DJ ST D2 D7 D8 C4 DQ D5 H5 DT HA 
CJ SA C3 C6 SQ D4 CQ C8 S6 D9 H6 SJ SK 
CT CK HK HT S7 S2 D6 H4 HQ H7 DA DK CA 
C9 S5 H2 C5 C2 H9 H8 S3 S8 S9 HJ H3 S4 
SJ C4 H6 C5 S5 H5 H4 H3 CJ S9 H7 C2 C8 
H8 D3 HA H9 DT S3 S8 S6 HT SA SK CK DK 
C9 SQ S7 D6 DJ CQ D5 C7 H2 CT C6 S2 D7 
D2 HK DA ST CA HJ C3 D9 DQ S4 HQ D4 D8 
CK DQ HK C6 DJ HA DK C5 SJ S3 H9 CQ S9 
HQ H5 C7 S8 CJ D7 D8 S5 H2 S4 H7 H6 ST 
CT S6 C2 D5 H3 SQ SA H4 CA DA D4 C4 C8 
HT S2 C9 DT D9 D6 D3 H8 D2 HJ SK C3 S7 
C3 D6 S2 CA S4 H4 DA CQ H5 H3 HQ SJ SK 
HT HK C2 CK C5 C6 D3 H7 S6 C4 ST SQ HJ 
D4 D5 S5 S8 H9 D2 DJ C8 H8 H2 DT HA D7 
DQ SA CT S9 H6 CJ D8 DK S7 D9 C7 S3 C9 
DA D9 SA CT C4 DQ S2 HK DT HJ S7 H3 H4 
C6 CQ ST H8 C3 S4 SK CA C5 D6 SJ C7 D7 
C8 H2 DK S3 CJ HA D2 S5 H5 S9 H6 C9 S8 
S6 HQ SQ D3 D5 HT D8 C2 D4 DJ H7 H9 CK 
C8 H2 HQ H8 H7 S3 S9 D9 S8 C5 D8 CA C3 
H5 S2 C7 ST D3 HT SA CT DQ DJ DT D5 HK 
C9 CJ DA CK C4 S4 SK HA H3 D4 H6 C2 SJ 
D2 H4 CQ D7 S6 H9 S5 S7 D6 SQ HJ C6 DK 
HK S7 HJ ST CJ H8 S5 SK S4 C6 SQ S8 DA 
C2 CQ S6 D8 H6 HQ D9 CA D6 DQ C5 C4 DK 
D4 H7 HT C7 D7 D3 H5 CK SA S9 H4 S3 C9 
DT C8 S2 H2 HA H9 D2 DJ CT C3 SJ H3 D5 
CK H3 SQ HQ DK C7 D5 H5 D8 ST H2 S3 S4 
C3 DJ S7 HK HA D3 C5 CQ S8 CJ D7 D9 C4 
D4 C9 CA SA H7 S2 S5 D6 DT HJ SK H6 S9 
CT H4 C6 HT D2 H8 H9 DQ C2 S6 DA SJ C8 
C8 C3 HA S3 H2 S6 H4 SK H8 CK S2 SA CJ 
H6 D6 DK D3 HK HT S5 S9 D8 D4 ST D7 S7 
CQ DJ D5 SQ H5 S8 D9 DT C7 C9 DQ CA SJ 
S4 HQ C5 C6 H7 C2 HJ CT DA D2 H3 C4 H9 
H2 CA HQ S7 C4 C2 S5 C8 DT DK S6 H8 H7 
D9 CQ S9 D2 CK D4 C5 D6 CJ D5 H3 H4 SJ 
H9 DQ SQ C7 ST C3 SK D3 SA C9 HK DJ S4 
S3 H6 HJ DA S2 S8 HT H5 CT D8 D7 HA C6 
C4 S4 SJ H2 H6 CQ ST HA S3 SA C7 D7 HT 
H9 H5 SQ C3 CK H3 CJ D9 D3 S9 DT CT S5 
D4 D6 DK DQ C6 HK C5 DA HJ D8 H4 S6 S8 
D5 C2 HQ C8 SK CA S7 C9 DJ D2 H7 H8 S2 
D7 DK D8 H6 C2 C5 S4 CT H8 H5 S6 S8 DQ 
CA HT S2 C6 H3 H7 S5 S7 D2 H4 HA HJ H9 
S9 HK DJ CK S3 D6 ST D9 SK HQ C7 H2 C8 
C4 SJ CQ DA CJ C9 SQ C3 D5 D4 DT SA D3 
S8 H3 CT D2 C3 C9 DQ H7 D9 C6 SJ S4 H8 
DA CQ C4 HA C5 H6 S5 H9 S6 DK SQ S7 CJ 
H5 S3 D3 H4 H2 SA S9 D4 DT S2 SK HT HK 
D6 C7 HJ ST DJ CK D7 CA D8 HQ C2 C8 D5 
H5 SA D2 D5 HJ C6 S3 SJ H8 H9 DJ H3 HA 
CQ C2 C8 D6 H6 CA SK D7 HK C7 D4 DQ CT 
H4 HQ S9 C9 DA C5 S5 DK S4 C3 D9 S8 D8 
C4 H2 CJ SQ DT S7 S2 HT H7 D3 S6 CK ST 
D8 SQ H4 SJ S8 S7 C7 S9 D3 CK DK S5 D6 
HJ CA CT D9 HK H8 C3 C6 DJ SA DA H7 H2 
S2 C5 CQ S4 SK S3 S6 D2 HA D7 D5 HT C4 
C9 ST D4 HQ CJ C2 DT H9 C8 H3 DQ H6 H5 
D6 H7 SA H3 D9 D7 DT D8 C6 CA S3 DA C8 
S2 CT CJ C7 SK SQ SJ C3 HQ S4 CK H9 H2 
C5 DQ H6 H5 C4 D5 ST S6 DK C2 S9 CQ H4 
S7 HK S8 HA D3 D2 S5 H8 DJ D4 HJ HT C9 
D6 SJ HQ S7 SQ HA H8 S6 H4 CJ H2 HJ CA 
C4 S2 HT H3 C8 DJ H9 HK S8 D7 SA C7 D4 
D2 C3 D9 S9 CT SK H6 D3 C5 DK S5 S4 H7 
D8 CQ DA DQ C6 C9 ST DT S3 CK C2 H5 D5 
H8 DQ HQ S9 S4 SK C3 HA D6 C4 D3 CQ S5 
H9 DK DA S7 CA C9 D7 H6 C7 C5 H7 H3 ST 
HK CT H5 D8 D9 C2 D2 C8 SJ SA S6 S2 SQ 
D4 DJ DT C6 HT H4 CK D5 S8 H2 CJ S3 HJ 
#