Two players share a counter that shows a non-negative integer. They move alternately. On a move the player looks at the decimal digits of the current value and subtracts from it either its largest digit or its smallest non-zero digit (the two may be the same digit). A player who faces the value 0 has no move and loses.
Call a starting value n cold if the player who moves first from n loses when both players play perfectly. Return how many cold values n satisfy lo <= n <= hi.
Examples
Input: lo = 1, hi = 100
Output: 10
Explanation: below 130 the cold values are exactly the multiples of 10.
Input: lo = 1, hi = 1000
Output: 303
Input: lo = 120, hi = 170
Output: 13
Explanation: 120, 130, 132, 140, 142, 150, 152, 154, 161, 163, 165, 167, 169.
Constraints
1 <= lo <= hi <= 10**18
Goals
- Classify game positions as winning or losing
- Recognise when a pattern cannot be extrapolated
- Compose memoised digit blocks to reach 10**18