847 - A Multiplication Game

Moderator: Board moderators

konsept
New poster
Posts: 22
Joined: Wed Dec 19, 2001 2:00 am
Contact:

847 - A Multiplication Game

Hi, I came up with a O( 9lg(n) ) algorithm for this problem, but it's not one of the fastest programs on the ranklist. It runs in 0.06seconds whereas most people do it in 0.00.
Can someone please explain how to solve this problem differently from the way i solved it (i just used basic dynamic programming)

[cpp]

#include <stdio.h>
#include <string.h>
#include <math.h>

unsigned int n;

// 2 3 5 7
char w[33][23][15][13];

char getwin( int two,int three,int five,int seven ){
if ( w[two][three][five][seven] != -1 )
return w[two][three][five][seven];

// base case

long double x=1.0;

x*=pow( 2.0, two );
x*=pow( 3.0, three );
x*=pow( 5.0, five );
x*=pow( 7.0, seven );

if ( x+0.00000001 >= (long double)n ) return 0;

// recursive case
int k=0;
k+=!getwin(two+1,three,five,seven); // 2
k+=!getwin(two,three+1,five,seven); // 3
k+=!getwin(two+2,three,five,seven); // 4
k+=!getwin(two,three,five+1,seven); // 5
k+=!getwin(two+1,three+1,five,seven); // 6
k+=!getwin(two,three,five,seven+1); // 7
k+=!getwin(two+3,three,five,seven); // 8
k+=!getwin(two,three+2,five,seven); // 9

return w[two][three][five][seven]= k>0;
}

void main( void ){
FILE *in=fopen( "mult.in", "r" );
int i,j,k;

while ( 1==fscanf( in, "%u", &n ) ){
memset( w, -1, sizeof(w) );
if ( getwin(0,0,0,0) ) printf( "Stan wins\n" );
else printf( "Ollie wins\n" );
}

}
[/cpp]

Cubist
New poster
Posts: 17
Joined: Sun May 26, 2002 7:56 am
Location: San Diego, CA
Consider the related game (e.g. taking the log of the numbers in this
problem) of A and B choosing real numbers in the interval [a,b].
Regardless of what the first player chooses, the 2nd player can
force the sum of the two numbers chosen to be a+b. Thus, if
the 2nd player (B) wins the game with sum S, they will also win the game
with sum S+(a+b). With a similar strategy if A wins with sum S,
A wins with sum S+(a+b). Being a little careful and inducting A
wins if k*(a+b) <= S <= b+k*(a+b) and B wins if
b+k*(a+b) < S < (k+1)*(a+b).

Translating this to the multiplication game gives you a criteria for
deciding which player wins with a given product P. Be careful with
numbers close to maxint, however.
Chris Long, San Diego Padres, 100 Park Boulevard, San Diego CA

My captain is Stanley Tweedle. I blow up planets for him.

Santiago Zanella
New poster
Posts: 10
Joined: Tue Oct 01, 2002 11:37 pm

Presentation Error

If I follow exactly the output specification of the statement I get a PE.
The output is in fact pretty simple:
Each line of input contains one integer number n. For each line of input output one line either
Stan wins.
or
Ollie wins.
I tried removing the dot at the end of each line and also removing the line feed but I always get a PE.
I noticed that there are a lot of Presentation Errors for this problem. Is there any kind of mistake in the output specification?

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan
Cubist wrote: Translating this to the multiplication game gives you a criteria for
deciding which player wins with a given product P.
Can you give more detail for the translation? I can understand the sum a+b. But I don't know what to do the multiplication. Thanks in advance.

New poster
Posts: 2
Joined: Tue Oct 08, 2002 12:35 pm
Just take input number and divide it by 9, then by 2, then by 9 and so on, until you reach 1. If you had odd number of ranges , one player wins, otherwise other player wins.

So solution requires at max 20 divisions, and can hardly be faster than that.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

If you don't understand, then write down all possible winning side number.

i.e ) number 1 - 9 : stan win
number 10 - 18 : ollie win
number 19 - 162 : stan win
and so on...

Because, it's the optimal strategy in this game. Why?

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

Help me 847 multiplication game

Hello, i need some help, can anyone tell me is my input outputs are correct? My code is always Wrong Answer

1 -> Stan wins.
2 -> Stan wins.
10 -> Ollie wins.
18 -> Stan wins.
19 -> Stan wins.
162 -> Stan wins.
163 -> Ollie wins.
1459 -> Stan wins.
13123 -> Ollie wins.
118099 -> Stan wins.
1062883 -> Ollie wins.
4294967295 -> Ollie wins.
Thank you for any help

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
Here is my output:
Ollie wins.
Stan wins.
Ollie wins.
Ollie wins.
Stan wins.
Stan wins.
Ollie wins.
Stan wins.
Stan wins.
Stan wins.
Ollie wins.
Stan wins.
I think the first and last input are invalid because 1 < n < 4294967295

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

I'm sorry

It seems that i've made a mistake when i wrote my sample input output
18 --> Ollie wins.
The differences between cytse's and mine are only
1--> Stan wins.
13123 --> Ollie wins.
4294967295 --> Ollie wins.
And since 1 or 4294967295 are invalid then the only thing I need to worry is 13123, why is it different than cytse's output. Have you got your's Accepted? Which one is correct ?

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
My program got AC, otherwise I won't post my output

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

now I'm really sorry

cytse, forgive me.. it's just doesn't make sense, why 13123 makes Stan the winner? Can you tell me why?

I guess this problem is a bit similar of making an AI program, right?

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
At first I thought of Minimax, and soon the problem is reduced to a simple math problem.

You may read other posts on this problem for more details
http://acm.uva.es/board/viewtopic.php?t=659

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

Thanks cytse...

Actually, i've read those posts before..and i didn't quite understand what they're saying....
i'm sorry cause i'm so stupid and so troubling you....
thx anyway cytse

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

847 - A Multiplication Game

Hi. Here is my code. Why it is not right?

[pascal]program A_Multiplication_Game;

var
n: Int64;

begin
while not eof do
begin
if n>774840978 then writeln('Stan wins.') else
if n>86093442 then writeln('Ollie wins.') else
if n>9565938 then writeln('Stan wins.') else
if n>1062882 then writeln('Ollie wins.') else
if n>118098 then writeln('Stan wins.') else
if n>13122 then writeln('Stan wins.') else
if n>1458 then writeln('Stan wins.') else
if n>162 then writeln('Ollie wins.') else
if n>18 then writeln('Stan wins.') else
if n>9 then writeln('Ollie wins.') else
if n>1 then writeln('Stan wins.');
end;
end.[/pascal]

Thanks.
_____________
NO sigNature

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Hi Farid,
There is a slight mistake in your assumption.
for 2 - 9 Stan wins------ correct
for 10 - 18 Ollie wins ----correct
for 19-162 Stan wins----correct
but from next on your program is not correct.
The next number is not always 9 times the previous number.