| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 643751 | beaconmc | Palindrome-Free Numbers (BOI13_numbers) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
def dp(flag,prev,prev2,d):
if d==cur:
return 1
if dps[flag][prev][prev2][d] != -1:
return dps[flag][prev][prev2][d]
ans = 0
if flag:
for i in range(sus[d+1]+1):
if prev==10 and i==0: i = 10
if i==prev and i!=10: continue
if i==prev2 and i!=10: continue
if i==sus[d+1]:
ans += dp(1,i,prev,d+1)
else:
ans += dp(0,i,prev,d+1)
else:
for i in range(10):
if prev==10 and i==0: i = 10
if prev == i and i!=10: continue
if i==prev2 and i!=10: continue
ans += dp(0,i,prev,d+1)
dps[flag][prev][prev2][d] = ans
return ans
a,b = map(int, input().split())
sus = [-1]+[int(i) for i in str(a)]
cur = len(sus)-1
dps= [[[[-1 for i in range(19)]for i in range(11)]for i in range(11)]for i in range(2)]
aa = dp(1,10,10,0)
sus = [-1]+[int(i) for i in str(b)]
cur = len(sus)-1
dps= [[[[-1 for i in range(19)]for i in range(11)]for i in range(11)]for i in range(2)]
bb = dp(1,10,10,0)
sus = [int(i) for i in str(a)]
flag = True
for i in range(len(sus)-1):
if sus[i] == sus[i+1]:
flag = False
aa -= flag
print(bb-aa)