847 - A Multiplication Game

[rbuchan]

A converse to this would be to start p = 1, then alternately multiplying it by 9, 2, 9, etc. Once p >= n, the problem is solved.

Cheers

[Maarten]

why 13123 makes Stan the winner?

My AC program makes Ollie the winner for 13123. In fact, I'd like to know very much your strategy to make Stan win. Wanna play a game of multiplication with n=13123? I will play Ollie, anyone volunteer to play Stan?

[Grazyna]

I read all the posts and I can not find where is the fault in my logic:

I read that is considered corect that from 18 -> 162 Stan wins.

Let them choose 50: Stan of course starts with 2. (Otherwise he looses since Ollie will return 81.) Ollie responds with 4. Stan now will return 8 or 36. In any case he will loose. So from 37 -> 72 Ollie wins.

Where is the mistake since accepted programs return the opposite?

[Grazyna]

I just got accepted assuming according to the advices of the forum that from 19 -> 162 Stan is winning. But still I think that judge is wrong on this problem...

[Jan]

I think u misunderstood the problem description..

You should know that Stan always starts with p=1. He does his multiplication with a number 2 - 9, then Ollie multiplies.

Code: Select all

For 50 Stan starts with 5, 
so p is 5
then Ollie can choose 2 or 9 (min or max respectively)
for 2 p will be 10 and for 9 p will be 45, and thus Stan wins.

For 37 Stan starts with 4,
so p is 4,
then Ollie can choose 2 or 9 (min or max respectively)
for 2 p will be 8 and for 9 p will be 36, and thus Stan wins again.

for 72 Stan starts with 7,
so p is 7,
then Ollie can choose 2 or 9 (min or max respectively)
for 2 p will be 14 and for 9 p will be 63, and thus Stan wins again.

for 18 Stan starts with 2 or 9 (min or max respectively),
so p will be 2 or 9,
then Ollie wins.

for 19 Stan starts with 2.
so p is 2,
then Ollie can choose 2 or 9 (min or max respectively)
for 2 p will be 4 and for 9 p will be 18, and thus Stan wins again.

Clear about the description? I hope so.

[Grazyna]

Thanks Jan for your reply and your nice explanation.
Everything is clear now , and it should be long time ago,
if I was more carefull. I misunderstood the problem, and I was so sure that I didn't bother myself to read the problem...

[willima]

I didn't understand this term. What does the problem mean when say that both players play perfectly in the game?

Thanks!

[renkinjutsushi]

The first time I read the problem I thought:

Let's call "p" the number in which we are right now and "n" the number I want to reach.

The first move I always must try is the biggest number available (i.e. 9)
If I can't win using the biggest number then:
I try the next biggest number "m" in which p * 9 * m < n

So I don't win, but I'm also sure that my opponent doesn't win either and I'm putting pressure so maybe I would won in my next turn.

Of course if

p * 9 * 2 > n

I have already lost.

I tried this logic but I got a WA.

Is there some hole in my logic?

[Debashis Maitra]

why WA

Code: Select all

Removed

[joy]

why WA

1 < n < 4294967295
so use unsigned int

[Debashis Maitra]

thanx joy u are right

[S.M. Arifuzzaman]

//my code(editted after Mr. Sohel's suggestion)
wa, plz help.

Code: Select all

/*********************************multiplicatation game****************/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

void main()
{
	//freopen("in847.txt","r",stdin);
	//freopen("out847.txt","w",stdout);
	long j,k=1,found=0;
	long long num,p,q;        

	while(scanf("%lld",&num)==1)
	{
		k=1,p=1,q=1,found=0;
		for(;!found;k++)
		{


				if(p*9>=num)
				{
					found=1;

					break;
				}
				else
				{
					for(j=9;j>=2;j--)
					{
						q=p*j;
						if(q*9>=num)
						{
							continue;
						}
						else
							break;
					}
					p=q;
				}

		}
		if(k%2)
		{
			printf("Stan wins.\n");
		}
		else
		{
			printf("Ollie wins.\n");
		}
	}


}

[sohel]

Looks like you are new in this forum.

1] Use the search option to find the existing threads on that problem and use that.

2] Posting the code without any explanation isn't usually a good idea.

3] Use the

Code: Select all

tags when posting codes.

4] For the title - mention the problem number and name. So your title should have been '847 - A multiplication game'

[S.M. Arifuzzaman]

Thnx Sohel bhai for ur valuable suggestion.

[S.M. Arifuzzaman]

Can anyone show me the bug in the code posted above??? I'd be really grateful. Plz...


I assume both stan and ollie will try with 9 to get p*9>=n. if fail, the will try with maximum p*j such that their counterpart will not be able to reach n by multiplying at most 9.