Submission #163352

---

Source Code Expand

from Queue import * # Queue, LifoQueue, PriorityQueue
from bisect import * #bisect, insort
from datetime import * 
from collections import * #deque, Counter,OrderedDict,defaultdict
#set([]) 
import calendar
import heapq
import math
import copy
import itertools
import string
myread = lambda : map(int,raw_input().split())
memo = [[[-1 for _ in xrange(2)]  for _ in xrange(2)] for _ in xrange(20)]
def dp_go(now,OK,in_49,num):
    if now == len(num):
        if in_49:
            return 1
        else:
            return 0
    if memo[now][OK][in_49] >= 0:
        return memo[now][OK][in_49]
    ret = 0
    if OK:
        for i in range(10):
            if i == 4 or i == 9:
                ret += dp_go(now+1,True,True,num)
            else:
                ret += dp_go(now+1,True,in_49,num)
    else:
        for i in range(int(num[now])):
            if i == 4 or i == 9:
                ret += dp_go(now+1,True,True,num)
            else:
                ret += dp_go(now+1,True,in_49,num)
        if num[now] == '4' or num[now] == '9':
            ret += dp_go(now+1,False,True,num)
        else:
            ret += dp_go(now+1,False,in_49,num)
    memo[now][OK][in_49] = ret
    return ret
def solver():
    global memo
    A,B = myread()
    a = dp_go(0,False,False,str(A-1))
    memo = [[[-1 for _ in xrange(2)]  for _ in xrange(2)] for _ in xrange(20)]
    b = dp_go(0,False,False,str(B))
    print b-a


if __name__ == "__main__":
    solver()
    

Submission Info

Judge Result