D - 禁止された数字 Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

たかはし王国の国王であるたかはし君主は数字の 4 と 9 が大嫌いです。それらの数字を国内で目にするだけで気分が悪いので、それらを使ってはいけないという法律を定めました。この法律を破ってしまうと罰せられます。数字が禁止されているので、ある数の10進表現を考えたとき、いずれかの桁に禁止された数字が1つでも含まれている場合、その数を使うことはできません。

今まで使っていた数字を使えなくなったあなたは、うっかり使ってしまって罰せられては困るので、使う可能性がある数の区間 [A,B]={A,A+1,A+2,...,B}[A,B]=\{A,A+1,A+2,...,B\} に、いくつ禁止された数が含まれているかを確かめることにしました。そのためのプログラムを作ってください。

部分点

この問題には2つのデータセットがあり、データセット毎に部分点が設定されている。

  • 1≦A≦B≦10,0001 ≦ A ≦ B ≦ 10,000 を満たすデータセット 1 に正解した場合は 3030 点が与えられる。
  • 追加制約のないデータセット 2 に正解した場合は、上記のデータセットとは別に 7070 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

AA BB
  • 11 行目には、整数 A,B(1≦A≦B≦1018)A,B (1≦A≦B≦10^{18}) が空白区切りで与えられる。

出力

区間 [A,B][A,B] に含まれる禁止された数がいくつ含まれているかを 11 行に出力せよ。出力の末尾に改行をいれること。

入力例1

Copy
  1. 1 9
1 9

出力例1

Copy
  1. 2
2

44 と 99 が禁止されています。

入力例2

Copy
  1. 40 49
40 49

出力例2

Copy
  1. 10
10

4040 ～ 4949 は全て禁止された数です。

入力例3

Copy
  1. 1 1000
1 1000

出力例3

Copy
  1. 488
488

入力例4

Copy
  1. 1 1000000000000000000
1 1000000000000000000

出力例4

Copy
  1. 981985601490518016
981985601490518016

2025-04-17 (Thu)
04:05:46 +00:00