제출 #731044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731044		Boomyday	Palindrome-Free Numbers (BOI13_numbers)	Pypy 3	20 / 100	70 ms	19952 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):
    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):
        d = len(x) - i

        #print(d, ch)
        val = int(ch)
        for cur in range(0, val):
            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))



#print(ans, ans_brute)

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