D - 禁止された数字
解説
/ 
/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
たかはし王国の国王であるたかはし君主は数字の 4 と 9 が大嫌いです。それらの数字を国内で目にするだけで気分が悪いので、それらを使ってはいけないという法律を定めました。この法律を破ってしまうと罰せられます。数字が禁止されているので、ある数の10進表現を考えたとき、いずれかの桁に禁止された数字が1つでも含まれている場合、その数を使うことはできません。
今まで使っていた数字を使えなくなったあなたは、うっかり使ってしまって罰せられては困るので、使う可能性がある数の区間 [A,B]=\{A,A+1,A+2,...,B\} に、いくつ禁止された数が含まれているかを確かめることにしました。そのためのプログラムを作ってください。
部分点
この問題には2つのデータセットがあり、データセット毎に部分点が設定されている。
- 1 ≦ A ≦ B ≦ 10,000 を満たすデータセット 1 に正解した場合は 30 点が与えられる。
- 追加制約のないデータセット 2 に正解した場合は、上記のデータセットとは別に 70 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
A B
- 1 行目には、整数 A,B (1≦A≦B≦10^{18}) が空白区切りで与えられる。
出力
区間 [A,B] に含まれる禁止された数がいくつ含まれているかを 1 行に出力せよ。出力の末尾に改行をいれること。
入力例1
1 9
出力例1
2
4 と 9 が禁止されています。
入力例2
40 49
出力例2
10
40 ～ 49 は全て禁止された数です。
入力例3
1 1000
出力例3
488
入力例4
1 1000000000000000000
出力例4
981985601490518016