This proof refers to http://www.algorithmist.com/index.php/UVa_10120
M=k2 1+3+5+7+…+(2k-1)=k2
Frank can easily reach the position k2, as long as he keeps moving forward.
When Frank is at R[x], the distance of the next jump will be 2k+1.
Proof 1.1 “If x-(2k+1)>=1 (indicating that jumping back will not exceed the boundary), Frank can reach R[x+2] (x+2<=M)”
If Frank jumps back (2k+1) and then jumps back (2k+3), the formula will be (x-(2k+1)+(2k+3))=(x+2).
And x-(2k+1)>=1 && (x+2)<=N, in short, just do not exceed the boundary.
Proof 1.2 “If Frank is at R[x], and then the distance of the next jump is 2k+1, as long as x-((2k+1)+(y-1)*2)>=1,
Frank can go from R[x] to R[x+2y] (0<=y and x+2y<=N)”
Assuming x-((2k+1)+(y-1)*2)>=1 (0<=y && x+2y<=N)
When y=0, x=x+2y, naturally we are at x.
When y=1, x - (2k+1) = x-((2k+1)+(y-1)*2) >= 1, from (proof 1.1) we can see that we can go from x to x+2.
When y>1, using induction, assume we can travel from x to x+2(y-1)=x+2y-2.
The assumption constraint is x-((2k+1)+(y-1)*2)>=1, if currently at x and the next step is 2k+1, it is as if we are currently at x+2(y-1).
And the next step is 2*(k+(y-1))+1, because we need two jumps to move x to x+2. To make the induction valid,
we need some constraints, the current point - the distance to the next step >=1, in this case, it is as if
(x+2(y-1)) - (2*(k+2(y-1))+1) >=1.
After some processing and transformation,
it will become x - (2_k_ + 1 + 2(y - 1)) >= 1, which is the same as our initial assumption, so this induction holds.
The proof is complete, now we move on to the implementation part of this problem, we need some methods to reach R[M].
These stones are arranged as follows: R[1], R[2], ... ,R[M],...
If M is odd, we let k also be odd, however, since the sequence of k becomes (1,9,25,49,81,...), it is strictly increasing.
So we can find an appropriate (k + 2)2 > M (it can definitely be found), then M>=k2.
When M is even, we also use the above method.
Now we find the range of k.
R[1], R[2], ..., R[k2], ..., R[M],...., R[(k + 2)2],....
Although M is unlikely to equal k2, if it does equal,
we can solve it using M=k2 1+3+5+7+…+(2k-1)=k2.
Since M - k2 must be even, and the earlier assumption is k2 <= M, we can let M=k2+2r, which means M=x+2y.
y equals (M-k2)/2.
So we can reach R[k2], the next step is 2k+1, then k2 - ((2k + 1) + 2(y - 1)) >= 1, we can reach R[M].
We can easily reach k2 because 1+3+5+7+…+(2k-1)=k2, and we can also easily reach R[M], but with conditions.
k2 - ((2k + 1) + 2(y - 1)) >= 1 y=(M-k2)/2.
After organizing, it becomes
2k2 - 2k + 1 - M >= 1.
And (k + 2)2 > M, strengthening the constraint condition, 2k2 - 2k + 1 - (k + 2)2 >= 1 will definitely make 2k2 - 2k + 1 - M >= 1.
And 2k2 - 2k + 1 - (k + 2)2 >= 1, after simplification, will become k_2 - 6_k - 4 >= 0.
Solving the binary inequality k >= 6.7 > (6+sqrt(36+16))/2.
And k2 <= M <= N, so N>=49 will always have a solution.
If not, just implement it directly.
//====================================================================||
// Name : Gift.cpp ||
// Date : 2013/5/25 上午9:59:29 ||
// Author : GCA ||
// 6AE7EE02212D47DAD26C32C0FE829006 ||
//====================================================================||
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE\_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%d ",dp\[htx\]\[hty\]);}Pln();}
#define M 10011
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define Is\_debug true
#define debug(...) if(Is\_debug)printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
int n,m;
struct node{
int now;
int njump;
node(int now,int njump):now(now),njump(njump){};
};
bool bfs(){
queue<node> q;
q.push(node(1,3));
while(!q.empty()){
int now=q.front().now;
int njump=q.front().njump;
if(now==m)return true;
q.pop();
if(now+njump<=n)q.push(node(now+njump,njump+2));
if(now-njump>0)q.push(node(now-njump,njump+2));
}
return false;
}
int main() {
ios\_base::sync\_with\_stdio(0);
while(~scanf("%d%d",&n,&m)&&n+m){
if(n>=49)printf("Let me try!\\n");
else{
if(bfs())printf("Let me try!\\n");
else printf("Don't make fun of me!\\n");
}
}
}