10120
Posted: Tue Feb 12, 2002 5:02 pm
I can solve it by using a recursion. But my program has TIME LIMIT EXCEEDED. Know anybody a better(faster) solution?
Page 1 of 2
Posted: Wed Feb 13, 2002 4:58 pm
Hi, you can try to use BFS.....
Posted: Mon Mar 04, 2002 2:51 pm
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>
<font size=-1>[ This Message was edited by: ahanys on 2002-04-02 12:04 ]</font>
10120 - Gift?!
Posted: Mon Oct 14, 2002 10:38 am
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]
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]
Posted: Mon Oct 14, 2002 5:06 pm
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
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
Posted: Thu Oct 31, 2002 8:29 am
Someone told me that if n>50 the answer is always "Let me try!"
Can anyone tell me how to prove it?
Can anyone tell me how to prove it?
Posted: Mon Jun 02, 2003 3:25 am
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.
Posted: Mon Jun 02, 2003 3:44 am
After running, I find out the primary situation that every stones can be
reached is n=49.
Posted: Sat Feb 28, 2004 5:15 pm
why it is possible to reach new stones if all old stones can be reached?
How do u proof this?
How do u proof this?
10120
Posted: Wed Jan 05, 2005 5:22 pm
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");
}
}
}
Posted: Wed Jan 05, 2005 6:58 pm
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");
}
}
}
10120 Gift
Posted: Thu Aug 03, 2006 2:26 pm
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
// code deleted after AC
Posted: Wed Aug 30, 2006 12:26 pm
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:
output:
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!
Posted: Sat Sep 02, 2006 8:15 am
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?
Posted: Thu Oct 26, 2006 8:41 pm
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.
I want to see the proof though.