Reachability of a point

Правка en5, от allthecode, 2017-03-29 03:35:44

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 time complexity better than O(x * y * n)?

Теги algorithm

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский allthecode 2017-03-29 03:35:44 5 Tiny change: 'lved with complexit' -> 'lved with time complexit'
en4 Английский allthecode 2017-03-29 03:35:31 77
en3 Английский allthecode 2017-03-28 12:11:54 8 Tiny change: 'm for this?' -> 'm for this problem?'
en2 Английский allthecode 2017-03-28 11:17:58 5 Tiny change: 'olynomial algorithm' -> 'olynomial time algorithm'
en1 Английский allthecode 2017-03-28 11:15:48 575 Initial revision (published)