10404 - Bachet's Game

[Alexey Talambutsa]

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
Read(N);
Read(K);

for i:=1 to K do begin
Read(W);
end;

Winner[0]:=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[20];
long Win[CST];
int flag;

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

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

Win[0] = 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]

Have you tried using SeekEof instead of Eof?

[ahanys]

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

[Whinii F.]

Check out Yarin's great post about game thoery problems.

http://acm.uva.es/board/viewtopic.php?t=1735

[eloha]

Can anyone post something more detail following the algorithm described by the above article for the first sample input:

20 1 3 8

[ACoimbra]

Hi,
SeekEof is a restricted function in the judge system, but you can do what I did,
[pascal]
While Not EoLn(Input) Do
Begin
Read(Input, N, M);
For I:=1 To M Do
Read(Input, Data);
ReadLn(Input);
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]

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
Readln;
Continue;
End;
........and what your code is
[/pascal]
Good luck.

[medv]

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
while eoln do readln;
read(n,m);
mas[0] := True;
for i:=1 to m do read(a[i]);readln;
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]

I don't know about bashe game, so i cant help you with that. But you can solve this problem with dynamic programming.

[jackie]

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]

hello..~
I already read this thread..

http://online-judge.uva.es/board/viewtopic.php?t=1735

but don't know how to apply it.. especially this part..

Code: Select all

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 

can anybody explain it with a simple example..?