D - 禁止された数字 Editorial /

Time Limit: 2 sec / Memory Limit: 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