oj.uz

Submission #731057

# Submission time Handle Problem Language Result Execution time Memory
731057 2023-04-26T21:17:58 Z Boomyday Palindrome-Free Numbers (BOI13_numbers) PyPy 3
10 / 100
 73 ms 19852 KB 
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] == 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
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 19368 KB Output isn't correct
2 Correct 49 ms 19416 KB Output is correct
3 Incorrect 55 ms 19600 KB Output isn't correct
4 Correct 46 ms 19484 KB Output is correct
5 Incorrect 47 ms 19428 KB Output isn't correct
6 Correct 48 ms 19392 KB Output is correct
7 Incorrect 55 ms 19364 KB Output isn't correct
8 Correct 49 ms 19372 KB Output is correct
9 Incorrect 49 ms 19416 KB Output isn't correct
10 Incorrect 49 ms 19452 KB Output isn't correct
11 Incorrect 51 ms 19388 KB Output isn't correct
12 Incorrect 53 ms 19400 KB Output isn't correct
13 Correct 54 ms 19416 KB Output is correct
14 Correct 48 ms 19436 KB Output is correct
15 Correct 50 ms 19400 KB Output is correct
16 Incorrect 57 ms 19560 KB Output isn't correct
17 Incorrect 59 ms 19588 KB Output isn't correct
18 Correct 68 ms 19424 KB Output is correct
19 Incorrect 62 ms 19640 KB Output isn't correct
20 Incorrect 52 ms 19492 KB Output isn't correct

Subtask #2
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 19596 KB Output isn't correct
2 Incorrect 57 ms 19716 KB Output isn't correct
3 Incorrect 57 ms 19652 KB Output isn't correct
4 Incorrect 56 ms 19736 KB Output isn't correct
5 Incorrect 55 ms 19564 KB Output isn't correct
6 Incorrect 56 ms 19588 KB Output isn't correct
7 Incorrect 56 ms 19624 KB Output isn't correct
8 Incorrect 71 ms 19588 KB Output isn't correct
9 Incorrect 56 ms 19368 KB Output isn't correct
10 Incorrect 64 ms 19440 KB Output isn't correct
11 Incorrect 58 ms 19608 KB Output isn't correct
12 Incorrect 54 ms 19584 KB Output isn't correct
13 Incorrect 52 ms 19632 KB Output isn't correct
14 Incorrect 69 ms 19564 KB Output isn't correct
15 Incorrect 59 ms 19616 KB Output isn't correct
16 Incorrect 67 ms 19784 KB Output isn't correct
17 Incorrect 54 ms 19800 KB Output isn't correct
18 Incorrect 60 ms 19696 KB Output isn't correct
19 Incorrect 62 ms 19708 KB Output isn't correct
20 Incorrect 72 ms 19676 KB Output isn't correct
21 Incorrect 70 ms 19728 KB Output isn't correct
22 Incorrect 67 ms 19616 KB Output isn't correct
23 Incorrect 70 ms 19732 KB Output isn't correct
24 Incorrect 61 ms 19680 KB Output isn't correct
25 Incorrect 58 ms 19752 KB Output isn't correct
26 Incorrect 64 ms 19624 KB Output isn't correct
27 Incorrect 64 ms 19768 KB Output isn't correct
28 Incorrect 63 ms 19736 KB Output isn't correct
29 Incorrect 68 ms 19668 KB Output isn't correct
30 Incorrect 53 ms 19716 KB Output isn't correct
31 Incorrect 54 ms 19664 KB Output isn't correct
32 Incorrect 67 ms 19716 KB Output isn't correct
33 Incorrect 64 ms 19692 KB Output isn't correct
34 Incorrect 59 ms 19752 KB Output isn't correct
35 Incorrect 52 ms 19852 KB Output isn't correct
36 Incorrect 68 ms 19624 KB Output isn't correct
37 Incorrect 60 ms 19708 KB Output isn't correct
38 Incorrect 54 ms 19596 KB Output isn't correct
39 Incorrect 66 ms 19720 KB Output isn't correct
40 Incorrect 57 ms 19668 KB Output isn't correct
41 Incorrect 53 ms 19720 KB Output isn't correct
42 Incorrect 65 ms 19764 KB Output isn't correct
43 Incorrect 53 ms 19752 KB Output isn't correct
44 Incorrect 52 ms 19748 KB Output isn't correct
45 Incorrect 73 ms 19716 KB Output isn't correct