ReverseAndIncrease

2017 TCO Semi 1 · 2017-03-31 · by cgy4ever

2017 TCO Semi 1 · 2017-03-31 · by cgy4ever · Math

Show categories

Class Name: ReverseAndIncrease

Return Type: String

Method Name: isPossible

Arg Types: (long long, long long)

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.

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
123456
Returns: "Impossible"

Watch out for overflow.

123456
1234567890123456
Returns: "Possible"

Submissions are judged against all 220 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ReverseAndIncrease with a public method string isPossible(long long s, long long t) · 220 test cases · 2 s / 256 MB per case