10404 - Bachet's Game

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10404 - Bachet's Game

Post by 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
New poster
Posts: 4
Joined: Fri Oct 26, 2001 2:00 am
Location: NTU Singapore
Contact:

Post by inteplus »

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

Post by ahanys »

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

Post by Whinii F. »

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

Post by 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
New poster
Posts: 14
Joined: Thu Apr 10, 2003 1:59 pm
Location: Coimbra, Portugal
Contact:

SeekEof is restricted

Post by 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
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by 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
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10404 Bashe Game. TLE! Wy?

Post by 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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by 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
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by 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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by 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..?

Post Reply

Return to “Volume 104 (10400-10499)”