ReverseAndIncrease | Topcoder Archive

Problem Statement

You have a display that shows a single positive integer in base 10. Initially, the value shown on the display is s. Your goal is to change that value to t.

You can change the value shown on the display by pressing buttons. There are two buttons attached to the display: a button labeled "increase" and a button labeled "reverse". Their effects are as follows:

Pressing the button "increase" increments the number shown on the display: if the current number is x, it changes to x+1.
The button "reverse" can only be pressed if the last digit of the current number is non-zero. Pressing this button reverses the digits of the number shown on the display. If the last digit of the current number is zero, this button is disabled.

You are given the longs s and t. Is there a sequence of zero or more button presses that changes s into t? Return "Possible" if such a sequence of actions exists, and "Impossible" if it does not exist.

Definition

Class:: ReverseAndIncrease
Method:: isPossible
Parameters:: long, long
Returns:: String
Method signature:: String isPossible(long s, long t)
(be sure your method is public)

Constraints

s will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.
t will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.

Examples

```
321
```
```
125
```
```
Returns: "Possible"
```
One possible solution is to push the buttons in the order "reverse, increase, increase". The number will change as follows: 321 -> 123 -> 124 -> 125.
```
120
```
```
21
```
```
Returns: "Impossible"
```
Note that we are not allowed to push the "reverse" button in this situation to change 120 into 021 = 21. In fact, we can easily prove that each number that can be obtained from 120 by pressing buttons will have at least three digits. Thus, producing 21 is impossible.
```
58
```
```
58
```
```
Returns: "Possible"
```
This time we don't need to push any button.

1234567890123456

Returns: "Impossible"

Watch out for overflow.

1234567890123456

Returns: "Possible"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.