MMM '14 D - Kuuhaku Numbers - Olympiads Online Judge

MMM '14 D - Kuuhaku Numbers

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 1.4s

Memory limit: 256M

Author:

FatalEagle

Problem type

Maniacal Midsummer Marathon 2014 by AL, TL, JJ

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$ $N$ digit KH-number in base- $10$ $10$ from left to right (most significant to least significant), there will exist a length $6$ $6$ subsequence of the digits that are nondecreasing in value. More formally: A number in the form $a_N \times 10^{N-1} + a_{N-1} \times 10^{N-2} + \dots + a_1 \times 10^0$ $a_{N} \times 10^{N - 1} + a_{N - 1} \times 10^{N - 2} + \dots + a_{1} \times 10^{0}$ has the sequence of digits $\{a_N, a_{N-1}, \dots, a_1\}$ ${a_{N}, a_{N - 1}, \dots, a_{1}}$ . This number is a KH-number iff there exists a sequence $\{c_1, c_2, \dots, c_k\}$ ${c_{1}, c_{2}, \dots, c_{k}}$ for $k \ge 6$ $k \geq 6$ , where $1 \le c_i \le N$ $1 \leq c_{i} \leq N$ (for $1 \le i \le k$ $1 \leq i \leq k$ ) and $c_i > c_{i+1}$ $c_{i} > c_{i + 1}$ and $a_{c_i} \le a_{c_{i+1}}$ $a_{c_{i}} \leq a_{c_{i + 1}}$ (for $1 \le i < k$ $1 \leq i < k$ ).

Shiro needs all the KH-numbers between $A$ $A$ and $B$ $B$ $(1 \le A \le B < 10^{18})$ $(1 \leq A \leq 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$ $A$ and $B$ $B$ to verify her calculations.

Input Specification

The $1^\text{st}$ $1^{st}$ line of input will contain the integer $A$ $A$ .
The $2^\text{nd}$ $2^{nd}$ line of input will contain the integer $B$ $B$ .
You can assume for test cases worth $30\%$ $30 %$ of points, $1 \le A \le B < 10^6$ $1 \leq A \leq B < 10^{6}$ .

Output Specification

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

Sample Input 1

Copy

111111
111131

Sample Output 1

Copy

Explanation for Sample 1

The valid KH-numbers are $111\,111$ $111 111$ , $111\,112$ $111 112$ , $111\,113$ $111 113$ , $111\,114$ $111 114$ , $111\,115$ $111 115$ , $111\,116$ $111 116$ , $111\,117$ $111 117$ , $111\,118$ $111 118$ , $111\,119$ $111 119$ , $111\,122$ $111 122$ , $111\,123$ $111 123$ , $111\,124$ $111 124$ , $111\,125$ $111 125$ , $111\,126$ $111 126$ , $111\,127$ $111 127$ , $111\,128$ $111 128$ , and $111\,129$ $111 129$ .

Sample Input 2

Copy

2454449
2454455

Sample Output 2

Copy

Explanation for Sample 2

The valid KH-numbers are $2\,454\,449$ $2 454 449$ and $2\,454\,455$ $2 454 455$ .

Sample Input 3

Copy

1111111
1111123

Sample Output 3

Copy

Explanation for Sample 3

All numbers between $1\,111\,111$ $1 111 111$ and $1\,111\,123$ $1 111 123$ are KH-numbers.

Comments

There are no comments at the moment.