oj.uz

답안 #731067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731067 2023-04-26T21:35:59 Z Boomyday Palindrome-Free Numbers (BOI13_numbers) PyPy 3
96.6667 / 100
 73 ms 19460 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]
    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 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)

        if val == chk[-2]:
            bad = True

        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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 19140 KB Output is correct
2 Correct 47 ms 19204 KB Output is correct
3 Correct 52 ms 19316 KB Output is correct
4 Correct 48 ms 19120 KB Output is correct
5 Correct 47 ms 19228 KB Output is correct
6 Correct 52 ms 19112 KB Output is correct
7 Correct 47 ms 19196 KB Output is correct
8 Correct 50 ms 19212 KB Output is correct
9 Correct 73 ms 19116 KB Output is correct
10 Correct 52 ms 19108 KB Output is correct
11 Correct 46 ms 19156 KB Output is correct
12 Correct 46 ms 19220 KB Output is correct
13 Correct 48 ms 19224 KB Output is correct
14 Correct 52 ms 19208 KB Output is correct
15 Correct 49 ms 19208 KB Output is correct
16 Correct 54 ms 19264 KB Output is correct
17 Correct 50 ms 19356 KB Output is correct
18 Correct 49 ms 19172 KB Output is correct
19 Correct 49 ms 19368 KB Output is correct
20 Correct 47 ms 19208 KB Output is correct

Subtask #2
71.6666666667 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 19412 KB Output is correct
2 Correct 54 ms 19368 KB Output is correct
3 Correct 56 ms 19360 KB Output is correct
4 Correct 53 ms 19368 KB Output is correct
5 Correct 57 ms 19308 KB Output is correct
6 Correct 50 ms 19364 KB Output is correct
7 Correct 59 ms 19444 KB Output is correct
8 Correct 61 ms 19368 KB Output is correct
9 Correct 58 ms 19220 KB Output is correct
10 Correct 63 ms 19188 KB Output is correct
11 Correct 54 ms 19352 KB Output is correct
12 Correct 50 ms 19332 KB Output is correct
13 Correct 51 ms 19292 KB Output is correct
14 Correct 51 ms 19320 KB Output is correct
15 Correct 47 ms 19356 KB Output is correct
16 Correct 53 ms 19324 KB Output is correct
17 Correct 52 ms 19288 KB Output is correct
18 Correct 51 ms 19292 KB Output is correct
19 Correct 51 ms 19368 KB Output is correct
20 Correct 55 ms 19320 KB Output is correct
21 Correct 50 ms 19284 KB Output is correct
22 Correct 51 ms 19320 KB Output is correct
23 Correct 50 ms 19360 KB Output is correct
24 Correct 54 ms 19328 KB Output is correct
25 Correct 55 ms 19400 KB Output is correct
26 Correct 54 ms 19340 KB Output is correct
27 Correct 50 ms 19360 KB Output is correct
28 Incorrect 53 ms 19328 KB Output isn't correct
29 Correct 50 ms 19352 KB Output is correct
30 Correct 51 ms 19460 KB Output is correct
31 Correct 51 ms 19368 KB Output is correct
32 Correct 50 ms 19376 KB Output is correct
33 Correct 56 ms 19368 KB Output is correct
34 Incorrect 48 ms 19336 KB Output isn't correct
35 Correct 57 ms 19436 KB Output is correct
36 Correct 51 ms 19364 KB Output is correct
37 Correct 52 ms 19340 KB Output is correct
38 Correct 56 ms 19276 KB Output is correct
39 Correct 51 ms 19356 KB Output is correct
40 Correct 48 ms 19316 KB Output is correct
41 Correct 57 ms 19372 KB Output is correct
42 Correct 50 ms 19384 KB Output is correct
43 Correct 52 ms 19376 KB Output is correct
44 Correct 55 ms 19344 KB Output is correct
45 Correct 58 ms 19300 KB Output is correct