#C8447. Reach Target in Exact Moves

    ID: 52430 Type: Default 1000ms 256MiB

Reach Target in Exact Moves

Reach Target in Exact Moves

Given five integers n, x, a, b, and y, you are required to determine whether it is possible to reach the target number y from the starting number x in exactly n moves.

In each move, you can either add a to your current number or subtract b from it. Mathematically, if you perform p additions and q subtractions (where p + q = n), the final value will be:

$$x + p\cdot a - q\cdot b = y$$

This equation can be rearranged to:

$$p\cdot (a+b) = y - x + n\cdot b$$

You need to decide if there exists an integer p (with 0 \leq p \leq n) satisfying the above equation. If such a p exists, output Possible; otherwise, output Impossible.

inputFormat

The input consists of a single line containing five integers separated by spaces:

n x a b y

Where:

  • n is the number of moves.
  • x is the starting number.
  • a is the amount added in a move if you choose addition.
  • b is the amount subtracted in a move if you choose subtraction.
  • y is the target number.

outputFormat

Output a single word: Possible if it is possible to reach y from x in exactly n moves using the allowed operations, or Impossible otherwise.

## sample
3 4 2 3 10
Possible