OJ Board

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]

Have you tried using SeekEof instead of Eof?

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

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

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

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

20 1 3 8

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.

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.

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.

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

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;

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..

can anybody explain it with a simple example..?