847 - A Multiplication Game

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

Moderator: Board moderators

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

847 - A Multiplication Game

Post by konsept » Fri Jun 21, 2002 12:40 am

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

Post by Cubist » Fri Jun 21, 2002 9:34 am

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

Post by Santiago Zanella » Tue Oct 01, 2002 11:49 pm

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

Post by yatsen » Wed Oct 02, 2002 3:30 pm

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.

Nenad
New poster
Posts: 2
Joined: Tue Oct 08, 2002 12:35 pm

Post by Nenad » Tue Oct 08, 2002 12:45 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:

Post by soyoja » Fri Nov 29, 2002 9:45 am

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

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

Help me 847 multiplication game

Post by Nick » Fri Apr 18, 2003 5:51 am

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

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Fri Apr 18, 2003 11:54 am

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

Post by Nick » Fri Apr 18, 2003 6:36 pm

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 ?

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Sat Apr 19, 2003 5:52 am

My program got AC, otherwise I won't post my output :P

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

now I'm really sorry

Post by Nick » Sun Apr 20, 2003 4:24 am

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?

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Sun Apr 20, 2003 6:54 pm

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

Post by Nick » Tue Apr 22, 2003 1:35 pm

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

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

847 - A Multiplication Game

Post by Farid Ahmadov » Thu Jun 26, 2003 5:16 pm

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:
_____________
NO sigNature

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Jul 01, 2003 1:06 pm

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.

Post Reply

Return to “Volume 8 (800-899)”