USA Compution Olympiad 2014 US OPEN, BLONZE
Problem 1: Odometer
原文 (English)
Farmer John's cows are on a road trip! The odometer on their car displays an integer mileage value, starting at X (100 <= X <= 10^16) miles at the beginning of their trip and ending at Y (X <= Y <= 10^16) miles at the end of their trip. Whenever the odometer displays an 'interesting' number (including at the start and end of the trip) the cows will moo. A number is 'interesting' if when you look at all its digits except for leading zeros, all of these are the same except for one single digit that is different. For example, the numbers 33323 and 110 are interesting, while the numbers 9779 and 55555 are not.
Help FJ count how many times the cows will moo during the trip.
For half of the test cases, the constraint X <= Y <= 10^6 will hold. Note that to store a number as large as 10^16, you will need a 64-bit integer data type such as a "long long" in C/C++.
和訳 (Japanese)
Farmer John の牛は、車で旅行中です！ 彼らの車の走行距離計には、整数の走行距離の値を表示します。 旅の開始時、走行距離計は X (100 ≦ X ≦ 1016) マイルを表示し、その旅の終了時には、Y (X ≦ Y ≦ 1016) マイルを表示します。 走行距離計が '面白い' 数値(旅の開始と終わりを含む) を表示するたびに、牛はモーと鳴きます。先頭のゼロを除いてすべての桁を見たときに、1つの桁を除いてすべての桁が同じであれば、その数は 面白いです。例えば、数値 33323 や 110 は面白いですが、9779 や 55555 は面白くありません。
旅行の間、牛が何度モーと鳴くか数えて、Farmer John を助けてください。
テストケースの半分は、制約 X ≦ Y ≦ 106を満たします。1016のような大きな数を保存するために、C/C++ で "long long" のような64-bit 整数型を必要とする点に注意してください。
入力形式
X Y
1行に半角スペースで区切られた X と Y が与えられる。
出力形式
1行に、牛がモーと鳴く回数を整数で出力せよ。
入出力例
入力例
110 133
出力例
13
解説
走行距離計は 旅行の開始時 110 を表示し、 133 を表示して終了している。牛は、{110, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 131, 133} の数値を読み、モーと鳴く。