## 10404 - Bachet's Game

Moderator: Board moderators

Alexey Talambutsa
New poster
Posts: 1
Joined: Tue Nov 12, 2002 2:43 pm
Location: Moscow

### 10404 - Bachet's Game

These two programs in Pascal and C solve task 10404 absolutely identically, but first (Pascal) get WA, and second (C) get Accepted.

Does anybody know, why it could be so?

[/pascal]
const
MN=2000000;

type
integer = longint;

var
N,K,i : integer;
W : array [1..20] of integer;
Winner : array [0..MN] of integer;

var
WW : longint;
A,ii : longint;
Good, canWin : boolean;

begin
while not eof do begin

for i:=1 to K do begin
end;

Winner:=1;

for A:=1 to N do begin
canWin:=False;
for ii:=1 to K do

if W[ii]<=A then
begin
if Winner[A-W[ii]]<>0 then begin
canWin:=True; break
end;
end;
if canWin then Winner[A]:=0 else Winner[A]:=1;
end;

if Winner[N]=0 then WriteLn('Stan wins') else WriteLn('Ollie wins');
end;
end.

[c]
#include <stdio.h>
#define CST 2000000

int main () {
long N,K,i,ii;

long W;
long Win[CST];
int flag;

while (scanf("%ld",&N)==1) {
scanf("%ld",&K);

for (i=K;i--;) {scanf("%ld",&W);}

Win = 1;
for (i=1;i<N+1;i++) {
flag = 0;

for (ii=K;ii--;) {
if (W[ii]<=i) {
if (Win[i-W[ii]]) {
flag=1;
break;
}
}
}

if (flag) Win=0; else Win=1;
}

if (Win[N]) printf("Ollie wins\n"); else printf("Stan wins\n");

}

return 0;
}[/code][/c]

inteplus
New poster
Posts: 4
Joined: Fri Oct 26, 2001 2:00 am
Location: NTU Singapore
Contact:
Have you tried using SeekEof instead of Eof?

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

### 10404

Please give me some idea to help me solve this problem.
Thanks

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### try..

Check out Yarin's great post about game thoery problems. http://acm.uva.es/board/viewtopic.php?t=1735

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
Can anyone post something more detail following the algorithm described by the above article for the first sample input:

20 1 3 8

ACoimbra
New poster
Posts: 14
Joined: Thu Apr 10, 2003 1:59 pm
Location: Coimbra, Portugal
Contact:

### SeekEof is restricted

Hi,
SeekEof is a restricted function in the judge system, but you can do what I did,
[pascal]
While Not EoLn(Input) Do
Begin
For I:=1 To M Do
Solve;
WriteData;
End;
[/pascal]

I know it seems stupid, but it works as it will only be in the Eoln when there is no more numbers in a line.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
Hey, Alexey.
You get WA because there are blank lines in the input.
You can change your code to
[pascal]
While not eof Do
Begin
If eoln Then
Begin
Continue;
End;
[/pascal]
Good luck.

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### 10404 Bashe Game. TLE! Wy?

Bashe Game
Wy TLE? How can I make my program more quicker?

program p10404;
const
MAX = 1000000;
MM = 10;
var
i,j,m,n:longint;
a:array[1..MM] of longint;
mas:array[0..MAX] of boolean;
flag:boolean;
begin
while not eof do
begin
mas := True;
for i:=1 to n do
begin
flag := False;
for j:=1 to m do
if (i - a[j] >= 0) and mas[i-a[j]] then
begin
flag := True; break;
end;
if flag then mas[i] := False else mas[i] := True;
end;
if mas[n] then write('Ollie ') else write('Stan ');
writeln('wins');
end;
end.

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
I don't know about bashe game, so i cant help you with that. But you can solve this problem with dynamic programming.

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
DP
[cpp]to compute number i(i <= n)
if exisit j(j < i) win[j] = true
&& exisit k(k >= 0 && k < m) i = j + choice[k]
then win = false

else
win = true; [/cpp]

if win = true
for (j = 0; j < m; ++j)
win[i+choice[j]] = false;

but

if win = false
no guarantee win[i + choice[j]] = true;

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
hello..~
``````b) If the popped state is winning for the player to move, then this move is bad from state x. Decrease the number of possible moves from state x. If this reaches 0, it means there are no moves from state x which will avoid a loss, thus mark state x as loss and add to queue