제출 #731062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731062		Boomyday	Palindrome-Free Numbers (BOI13_numbers)	Pypy 3	26.67 / 100	71 ms	19844 KiB

numbers

a, b = map(int, input().split())




dp = [[[0 for i in range(11)] for i in range(11)] for i in range(20)]
dp[0][10][10] = 1


for dig in range(1, 19):

    for cur in range(10):
        for prev in range(11):
            if cur == prev:

                continue
            for prev2 in range(11):
                if prev2 == cur:

                    continue
                dp[dig][cur][prev] += dp[dig-1][prev][prev2]


## dig = 1


##d = 5


"""
ans = 1
for dig in range(1, d+1):
    for cur in range(1, 11):
        for prev in range(11):
            ans += dp[dig][cur][prev]

"""


def solve(x):

    if x == 0:
        return 0
    ans = 1
    x = list(str(x))

    for dig in range(1, len(x)):
        for cur in range(1, 11):
            for prev in range(11):
                ans += dp[dig][cur][prev]

    #print(ans)

    chk = [11,11]
    for i, ch in enumerate(x):
        #if i == len(x)-1:   continue
        d = len(x) - i

        #print(d, ch)
        val = int(ch)
        for cur in range(0, val):
            if chk[-1] == chk[-2] and chk[-1] != 11: continue
            if chk[-1] == 11 and cur == 0:
                continue
            if cur == chk[-1] or cur == chk[-2]:
                continue
            for prev in range(11):
                if prev == chk[-1]: continue
                ans += dp[d][cur][prev]

        #print(ans)
        chk[-2] = chk[-1]
        chk[-1] = val

    return ans


print(solve(b+1)-solve(a))


"""
ans_brute = 0

for n in range(a, b+1):
    st = str(n)
    is_pal = False

    for l in range(len(st)):
        for r in range(l+2, len(st)+1):
            if st[l:r] == st[l:r][::-1]:
                is_pal = True

    if not is_pal:
        ans_brute+=1


print(ans_brute)
#print(ans, ans_brute)"""

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