Algorithms and Data Structures

The Remainder Game

Let’s play a game. Given an initial number and two sequences , , you should get from to 0 as fast as possible. On each step, you are allowed to pick an index i and apply the following operation on the current number:
This way, you’ll obtain the next number. You should find the minimum number of operations that would get you from to 0.


The first line of the input contains 3 integers n, m, and (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000, and 0 < < m).
The next n lines contain a pair of integers (0 ≤ , ).


The program should print the minimum number of operations to get from to 0. If it’s impossible to get to 0, the program should print Impossible.


2 5 1 3 1 2 1


Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue