Submission #643753

#	Time	Username	Problem	Language	Result	Execution time	Memory
643753		beaconmc	Palindrome-Free Numbers (BOI13_numbers)	Pypy 3	100 / 100	88 ms	21664 KiB

numbers

def palin(x):
    x = str(x)
    for i in range(len(x)-1):
        if x[i] == x[i+1]: return True
    for i in range(len(x)-2):
        if x[i] == x[i+2]: return True
    return False

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)


if not palin(a):
    aa -= 1
print(bb-aa)

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75