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.
Is there even a polynomial time algorithm for this?
