10120 - Gift?!

[ahanys]

I can solve it by using a recursion. But my program has TIME LIMIT EXCEEDED. Know anybody a better(faster) solution?

[..]

Hi, you can try to use BFS.....

[ahanys]

Why if m,n>50 then print "try it"?


<font size=-1>[ This Message was edited by: ahanys on 2002-04-02 12:04 ]</font>

[yatsen]

Can anyone tell me what is wrong?
I got Time Limit Exceeded.
[c]#include <stdio.h>
char GotGift;
long N,M;
void jump(long p,long i)
{
if (p==M)
{ GotGift=1; return; }
if (p>N || p<1)
return;
jump(p+(2*i-1),i+1);
if (!GotGift)
jump(p-(2*i-1),i+1);
}

main()
{
while (1)
{
scanf("%ld %ld",&N,&M);
if(N==0 && M==0) break;
GotGift=0;
jump(1,2);
if (GotGift) printf("Let me try!\n");
else printf("Don't make fun of me!\n");
}
return 0;
}
[/c]

[Yarin]

Your program doesn't work very well on large inputs, for instance

1000000 34238

In this problem you can handle big inputs in a special way; if there are enough stones it's always possible to reach a certain stone. Why this is so I don't want to prove

[eloha]

Someone told me that if n>50 the answer is always "Let me try!"
Can anyone tell me how to prove it?

[Ghost77 dimen]

I think mathematical induction a good explanation.

If you can find a situation that every stone can be reached,

then you can start from every stone you have been to fill the new stones.

It is always possible. What you should do now is only to find out the

primary situation.

[Ghost77 dimen]

After running, I find out the primary situation that every stones can be

reached is n=49.

[lky]

why it is possible to reach new stones if all old stones can be reached?
How do u proof this?

[CodeMaker]

can anyone give me 2 or 3 extrem i/o for this problem?

Code: Select all

#include<stdio.h>

void main()
{
	int m,n,i,p[100000],x,y,count,flage;

	while(scanf("%d%d",&n,&m) && m && n)
	{
		if(n>=49 || m==1)
			printf("Let me try!\n");
		else
		{
			count=1;
			p[count++]=1;

			flage=0;
			for(i=1;i<count;i++)
			{
				x=p[i]-2*(i+1)+1;
				y=p[i]+2*(i+1)-1;

				if(x<=n && x>=0)
				{

					if(x==m)
					{
						printf("Let me try!\n");
						flage=1;
						break;
					}
					else
					{
						p[count++]=x;
					}
				}
				else if(y<=n && y>=0)
				{
					if(y==m)
					{
						printf("Let me try!\n");
						flage=1;
						break;
					}
					else
					{
						p[count++]=y;
					}
				}
				else
				{
					break;
				}
			}
			if(!flage)
				printf("Don't make fun of me!\n");
		}
	}
}

			

[CodeMaker]

Hi ,I changed it in recursive method, still wrong answer.....

Code: Select all

#include<stdio.h>
int n,m;

int check(int v,int i)
{
	int x,y;

	x=v+2*i-1;
	y=v-2*i+1;

	if(x==m || y==m)
		return 1;

	if(x>0 && x<=n)
	{
		if(check(x,i+1))
			return 1;
		else
			return 0;
	}
	else if(y>0 && y<=n)
	{
		if(check(y,i+1))
			return 1;
		else
			return 0;
	}
	return 0;
}

void main()
{
	while(scanf("%d%d",&n,&m) && m && n)
	{
		if(n>50 || m==1)
			printf("Let me try!\n");
		else
		{
			if(check(0,1))
				printf("Let me try!\n");
			else
				printf("Don't make fun of me!\n");
		}
	}
}

[taskin]

i think this problem can be solved by using bfs. but my following code give wa. can anyone help? my idea is wrong or i just made wrong implementation of bfs?

// code deleted after AC

[CodeMaker]

Hi, your code has some problem.

consider the case: 49 49 , surely it is reachable.
1+3+5+7+9+11+13 =49

the fact is that, there can be 2 nodes in the same level of your bfs tree, but you don't have any information of that, u just consider them as they are in different level.


Input:

Code: Select all

1000000 999999
1000000 10
1000000 6
101     101
33      33
19      19
1000000 1
1000000 2
1000000 3
1000000 4
1000000 5
1000000 7
1000000 8
1000000 9
1000000 1000000
1000000 900000
1000000 111111
123456  123456
707     49
707     505
21      20
125     124
111111  2222
16      15
12      2
49      49
10      1
9       5
303030  5064
17      17
808805  47566
0       0

output:

Code: Select all

Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Don't make fun of me!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Let me try!
Don't make fun of me!
Let me try!
Let me try!
Let me try!
Don't make fun of me!
Let me try!
Don't make fun of me!
Let me try!

[taskin]

thanks. but if i dont use special case (for n > 49, result always let me try) then it only results MLE. so i had to use special checking. is there any way to solve this without this special checking?

[yiuyuho]

It would seem that you can prove that the frog can always reah any location once n>=49. Thus, it is not really a "special coded" solution.

I want to see the proof though.