### Maniacal Midsummer Marathon 2014 by AL, TL, JJ

## Problem D: Kuuhaku Numbers

Shiro is enthralled by the latest FPS (first person shooter) game in the Eastern Federation. A lot is riding on this game, so she is planning to snipe the other player, Izuna, for a decisive victory. Shiro plans to pull this off from a kilometer away, and Izuna is in a shelter, so this requires very advanced mathematical calculations. Shiro needs a special sequence of numbers, the *Kuuhaku numbers* (a.k.a. KH-numbers) to accomplish her goal.

The KH-numbers have an interesting property: examining each digit of an `N` digit KH-number in base-10 from left to right (most significant to least significant), there will exist a length 6 subsequence of the digits that are nondecreasing in value. More formally: A number in the form `a`_{N}×10^{N−1} + `a`_{N−1}×10^{N−2} + … + `a`_{1}×10^{0} has the sequence of digits {`a`_{N}, `a`_{N−1}, …, `a`_{1}}. This number is a KH-number iff there exists a sequence {`c`_{1}, `c`_{2}, …, `c _{k}`} for

`k`≥ 6, where 1 ≤

`c`≤

_{i}`N`(for 1 ≤

`i`≤

`k`) and

`c`>

_{i}`c`

_{i + 1}and

`a`≤

_{ci}`a`

_{ci + 1}(for 1 ≤

`i`<

`k`).

Shiro needs all the KH-numbers between `A` and `B` (1 ≤ `A` ≤ `B` < 10^{18}) to complete her calculations. In the time you need to compute all those numbers, she is sure that she can calculate the exact numbers in her head. Therefore, Shiro only needs you to determine the number of KH-numbers that exist between `A` and `B` to verify her calculations.

### Input Format

The 1st line of input will contain the integer `A`.

The 2nd line of input will contain the integer `B`.

You can assume for test cases worth 30% of points, 1 ≤ `A` ≤ `B` < 10^{6}.

### Output Format

A single integer, the number of KH-numbers between `A` and `B`, inclusive.

### Sample Input 1

111111 111131

### Sample Output 1

17

### Explanation for Sample 1

The valid KH-numbers are 111111, 111112, 111113, 111114, 111115, 111116, 111117, 111118, 111119, 111122, 111123, 111124, 111125, 111126, 111127, 111128, and 111129.

### Sample Input 2

2454449 2454455

### Sample Output 2

2

### Explanation for Sample 2

The valid KH-numbers are 2454449 and 2454455.

### Sample Input 3

1111111 1111123

### Sample Output 3

13

### Explanation for Sample 3

All numbers between 1111111 and 1111123 are KH-numbers.

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 3.00s

**Memory Limit:** 256M

**Added:** Jul 15, 2014

**Author:** FatalEagle

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...