Reachability of a point

Revision en4, by allthecode, 2017-03-29 03:35:31

You are in position (0, 0) of a coordinate plane. You want to determine if you can reach point (x, y). There are n different types of steps that you can make. Step type i is represented by two non-negative integers ai, bi which means that a step of type i moves you ai steps to the right and bi steps up.

How to determine if it is possible to reach point (x, y) using only those type of steps? You are allowed to use a type of step multiple times but you can't do half of a step.

Can this problem be solved with complexity better than O(x * y * n)?

Tags algorithm

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English allthecode 2017-03-29 03:35:44 5 Tiny change: 'lved with complexit' -> 'lved with time complexit'
en4 English allthecode 2017-03-29 03:35:31 77
en3 English allthecode 2017-03-28 12:11:54 8 Tiny change: 'm for this?' -> 'm for this problem?'
en2 English allthecode 2017-03-28 11:17:58 5 Tiny change: 'olynomial algorithm' -> 'olynomial time algorithm'
en1 English allthecode 2017-03-28 11:15:48 575 Initial revision (published)