Page 1 of 3

847 - A Multiplication Game

Posted: Fri Jun 21, 2002 12:40 am
by konsept
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]

Posted: Fri Jun 21, 2002 9:34 am
by Cubist
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.

Presentation Error

Posted: Tue Oct 01, 2002 11:49 pm
by Santiago Zanella
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?

Posted: Wed Oct 02, 2002 3:30 pm
by yatsen
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.

Posted: Tue Oct 08, 2002 12:45 pm
by Nenad
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.

Posted: Fri Nov 29, 2002 9:45 am
by soyoja
Nenad's comment was exactly right.

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? :)

Help me 847 multiplication game

Posted: Fri Apr 18, 2003 5:51 am
by Nick
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

Posted: Fri Apr 18, 2003 11:54 am
by cytse
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

I'm sorry

Posted: Fri Apr 18, 2003 6:36 pm
by Nick
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 ?

Posted: Sat Apr 19, 2003 5:52 am
by cytse
My program got AC, otherwise I won't post my output :P

now I'm really sorry

Posted: Sun Apr 20, 2003 4:24 am
by Nick
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?

Posted: Sun Apr 20, 2003 6:54 pm
by cytse
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

Thanks cytse...

Posted: Tue Apr 22, 2003 1:35 pm
by Nick
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

847 - A Multiplication Game

Posted: Thu Jun 26, 2003 5:16 pm
by Farid Ahmadov
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. :cry: :cry:

Posted: Tue Jul 01, 2003 1:06 pm
by sohel
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.