Submission #731066

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
731066	2023-04-26T21:31:17 Z	Boomyday	Palindrome-Free Numbers (BOI13_numbers)	PyPy 3	66.25 / 100	65 ms	19472 KB

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]
    bad = False
    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 bad:
                continue
            if chk[-1] == chk[-2] and chk[-1] != 11:
                bad = True
                continue

            if val == chk[-2]:
                bad = True
                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

21.25 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	19112 KB	Output is correct
2	Correct	53 ms	19208 KB	Output is correct
3	Correct	50 ms	19308 KB	Output is correct
4	Correct	49 ms	19188 KB	Output is correct
5	Correct	50 ms	19200 KB	Output is correct
6	Correct	53 ms	19296 KB	Output is correct
7	Correct	51 ms	19192 KB	Output is correct
8	Correct	53 ms	19220 KB	Output is correct
9	Correct	49 ms	19184 KB	Output is correct
10	Correct	65 ms	19160 KB	Output is correct
11	Incorrect	49 ms	19108 KB	Output isn't correct
12	Correct	52 ms	19144 KB	Output is correct
13	Correct	60 ms	19196 KB	Output is correct
14	Correct	52 ms	19308 KB	Output is correct
15	Correct	52 ms	19220 KB	Output is correct
16	Incorrect	62 ms	19276 KB	Output isn't correct
17	Incorrect	51 ms	19272 KB	Output isn't correct
18	Correct	51 ms	19200 KB	Output is correct
19	Correct	54 ms	19328 KB	Output is correct
20	Correct	50 ms	19220 KB	Output is correct

Subtask #2

45.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	19360 KB	Output is correct
2	Incorrect	56 ms	19372 KB	Output isn't correct
3	Incorrect	54 ms	19348 KB	Output isn't correct
4	Incorrect	55 ms	19332 KB	Output isn't correct
5	Correct	57 ms	19244 KB	Output is correct
6	Correct	50 ms	19284 KB	Output is correct
7	Correct	63 ms	19240 KB	Output is correct
8	Correct	58 ms	19332 KB	Output is correct
9	Incorrect	47 ms	19248 KB	Output isn't correct
10	Incorrect	50 ms	19184 KB	Output isn't correct
11	Correct	48 ms	19348 KB	Output is correct
12	Correct	60 ms	19356 KB	Output is correct
13	Correct	62 ms	19324 KB	Output is correct
14	Correct	52 ms	19412 KB	Output is correct
15	Incorrect	54 ms	19344 KB	Output isn't correct
16	Incorrect	54 ms	19332 KB	Output isn't correct
17	Correct	50 ms	19356 KB	Output is correct
18	Correct	54 ms	19340 KB	Output is correct
19	Correct	52 ms	19312 KB	Output is correct
20	Correct	49 ms	19300 KB	Output is correct
21	Incorrect	51 ms	19324 KB	Output isn't correct
22	Correct	50 ms	19388 KB	Output is correct
23	Incorrect	51 ms	19392 KB	Output isn't correct
24	Correct	49 ms	19332 KB	Output is correct
25	Incorrect	52 ms	19332 KB	Output isn't correct
26	Incorrect	53 ms	19336 KB	Output isn't correct
27	Correct	51 ms	19288 KB	Output is correct
28	Incorrect	65 ms	19324 KB	Output isn't correct
29	Correct	53 ms	19332 KB	Output is correct
30	Correct	49 ms	19368 KB	Output is correct
31	Correct	62 ms	19416 KB	Output is correct
32	Correct	64 ms	19368 KB	Output is correct
33	Correct	53 ms	19340 KB	Output is correct
34	Correct	63 ms	19348 KB	Output is correct
35	Correct	52 ms	19472 KB	Output is correct
36	Incorrect	51 ms	19300 KB	Output isn't correct
37	Correct	52 ms	19380 KB	Output is correct
38	Incorrect	50 ms	19368 KB	Output isn't correct
39	Incorrect	57 ms	19368 KB	Output isn't correct
40	Correct	54 ms	19316 KB	Output is correct
41	Correct	54 ms	19304 KB	Output is correct
42	Correct	50 ms	19368 KB	Output is correct
43	Incorrect	49 ms	19368 KB	Output isn't correct
44	Incorrect	54 ms	19352 KB	Output isn't correct
45	Incorrect	54 ms	19328 KB	Output isn't correct