(SRM 514 250) In this problem n or m will be 1 and there is a elegant conclusion to solve this problem -- if you have a (1,even),you can go any girds,and if you have a (1,odd),you can go to any girds(x,y) which x+y is even
Given a set of valid jumps,can go from (0,0) to (X,Y)?
it seems to find a integer root of these equations:
n1*k1+n1*k2-n1*k3-n1*k4+m1*k5+m1*k6-m1*k7-m1*k8+n2*k9...=X
m1*k1-m1*k2+m1*k3-m1*k4+n1*k5-n1*k6+n1*k7-n1*k8+m2*k9...=Y
ki means performs the (i%8)-th directions of (i/8+1)-th jump-types ki times.
if the set of jumps is {(1,2)} and X=5 Y=4,the equations will be like that:
k1+k2-k3-k4+2*k5+2*k6-2*k7-2*k8=5
2*k1-2*k2+2*k3-2*k4+k5-k6+k7-k8=4
a integer root of that equations is k1=1,k5=2,k2=k3=k4=k6=k7=k8=0.
(1+2*2=5 2+2*1=4)
that means (0,0)->(1,2)->(3,3)->(5,4)
but i can't solve equations like this...or there may be a more elegant algorithms to solve this problem?
sorry for my poor English.
————————
if there is one element in jump set,it just the same as this problem:
http://acm.timus.ru/problem.aspx?space=1&num=1286
http://acm.timus.ru/problem.aspx?space=1&num=1286
----------------
I just thought out a 2^(2n)(n is the size of valid jumps set) algorithm to solve this problem,but not to solve this equations.
assume (ni,mi) is the ith jump type.
first of all,I notice that you can go from (0,0) to (0,2*ni) and (0,2*mi).
that is the point (0,X) which 2k1n1+2k2m1+2k3n2+2k4m2..=X is reachable.
it can be proved that X=k*gcd(2*n1,2*m1,2*n2,2*m2...).
let g=gcd(n1,m1,n2,m2...)
you can go from (0,0) to (0,k*2g).
Similarly, (k*2g,0) is reachable.
So,(k1*2g,k2*2g) is reachable.
if the destination point is in (2k1*g,2k2*g) so the answer will be yes.
any jumps performs twice will go from a (2k1*g,2k2*g) to another (2k1*g,2k2*g),
and the point ignored is the point from a (2k1*g,2k2*g) reached by perform no two same jumps.
So,we just enumerate the ways of single jumps and just to calculate the destination whether to be reach by single jumps from (2k1*g,2k2*g).
there is 2^2n ways.
assume (ni,mi) is the ith jump type.
first of all,I notice that you can go from (0,0) to (0,2*ni) and (0,2*mi).
that is the point (0,X) which 2k1n1+2k2m1+2k3n2+2k4m2..=X is reachable.
it can be proved that X=k*gcd(2*n1,2*m1,2*n2,2*m2...).
let g=gcd(n1,m1,n2,m2...)
you can go from (0,0) to (0,k*2g).
Similarly, (k*2g,0) is reachable.
So,(k1*2g,k2*2g) is reachable.
if the destination point is in (2k1*g,2k2*g) so the answer will be yes.
any jumps performs twice will go from a (2k1*g,2k2*g) to another (2k1*g,2k2*g),
and the point ignored is the point from a (2k1*g,2k2*g) reached by perform no two same jumps.
So,we just enumerate the ways of single jumps and just to calculate the destination whether to be reach by single jumps from (2k1*g,2k2*g).
there is 2^2n ways.
Considering my poor English, I take a example to illustrate my algorithm.
let jumps set={(1,even)},the g=1.2*g=2.
so the (even,even) is reachable.
and the single move and combinations will be (1,even) (even,1) (even+1,even+1)<-that is the combinations of moves of first two type .
case1:if destination is (even,even), it obviously can be reached.
case2:if destination is (even,odd), it minus (even,1) leaves a (even,even).that is to say,we perform a single (even,1) and then perform some double same moves can get the destination.
case3:if destination is (odd,even),it just similar to case 2.
case4:if destination is (odd,odd),we minus (even+1,even+1) and we also get (even,even).
So,(1,even) can go anywhere.
————————
there is a more elegant algorithm.That is O(nlogn).The main idea is compressed the space by g.
by venkateshb.
How about this:
Let g=gcd(m1,n1,m2,n2,....)
Now, if X%g != 0 or Y%g != 0, then we do not have a solution.
So now, you can divide X, Y, m1, n1, m2, n2, ... all of them by g.
Now, if (X+Y)%2==0, then we have a solution
Otherwise, if atleast one of the (mi+ni)%2!=0, then also we have a solution
Otherwise, we do not have a solution.
Let g=gcd(m1,n1,m2,n2,....)
Now, if X%g != 0 or Y%g != 0, then we do not have a solution.
So now, you can divide X, Y, m1, n1, m2, n2, ... all of them by g.
Now, if (X+Y)%2==0, then we have a solution
Otherwise, if atleast one of the (mi+ni)%2!=0, then also we have a solution
Otherwise, we do not have a solution.
case is same as m == 1 or n == 1
else :
If X and Y, both are divisible by gcd(m,n):
simplify problem by dividing by gcd => case is same as m == 1 or n == 1
else
NO