847  A Multiplication Game
Moderator: Board moderators
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]
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]
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.
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.
My captain is Stanley Tweedle. I blow up planets for him.

 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:
I noticed that there are a lot of Presentation Errors for this problem. Is there any kind of mistake in the output specification?
The output is in fact pretty simple:
I tried removing the dot at the end of each line and also removing the line feed but I always get a PE.Each line of input contains one integer number n. For each line of input output one line either
Stan wins.
or
Ollie wins.
I noticed that there are a lot of Presentation Errors for this problem. Is there any kind of mistake in the output specification?
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
Thank you for any help
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.
I'm sorry
It seems that i've made a mistake when i wrote my sample input output
The differences between cytse's and mine are only18 > 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 ?1> Stan wins.
13123 > Ollie wins.
4294967295 > Ollie wins.
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?
I guess this problem is a bit similar of making an AI program, right?
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
You may read other posts on this problem for more details
http://acm.uva.es/board/viewtopic.php?t=659
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
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?
Please help.
[pascal]program A_Multiplication_Game;
var
n: Int64;
begin
while not eof do
begin
read(n);
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.
Please help.
[pascal]program A_Multiplication_Game;
var
n: Int64;
begin
while not eof do
begin
read(n);
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
NO sigNature