Submission #53488951

Source Code Expand

N, K = map(int, input().split())
D = list(map(int, input().split()))

len_ = len(str(N))
is_use = set([i for i in range(10)]) ^ set(D)
max_num = max(is_use)
INF = int(str(max_num)*len_)
if INF < N:
    len_ += 1
    INF *= 10
    INF += max_num

# dp[i][S] := 上から i 桁目までで集合 S (1~9) で作れる N 以上の最小値
dp =[[INF]*(1 << 10) for _ in range(len_ + 1)]

for i in range(len_):
    for S in range(1 << 10):
        for j in range(10):
            cnt = list(str(dp[i][S]))
            cnt[i] = str(j)
            cnt = int("".join(cnt))
            if cnt >= N:
                dp[i + 1][S | (1 << j)] = min(dp[i + 1][S | (1 << j)], cnt)

ans = INF
use_bin = sum([(1 << i) for i in is_use])
for i in range(1 << 10):
    ans = min(ans, dp[len_][i & use_bin])

print(ans)

Submission Info

Submission Time
Task C - Iroha's Obsession
User ryusuke_h
Language Python (PyPy 3.10-v7.3.12)
Score 300
Code Size 826 Byte
Status AC
Exec Time 80 ms
Memory 83360 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status AC
AC × 10
Set Name Test Cases
Sample
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_X_01.txt, subtask1_X_02.txt, subtask1_X_03.txt, subtask1_X_04.txt, subtask1_X_05.txt, subtask1_X_06.txt, subtask1_X_07.txt, subtask1_X_08.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 77 ms 83104 KiB
subtask0_sample_02.txt AC 74 ms 83148 KiB
subtask1_X_01.txt AC 78 ms 83220 KiB
subtask1_X_02.txt AC 80 ms 83360 KiB
subtask1_X_03.txt AC 77 ms 83160 KiB
subtask1_X_04.txt AC 74 ms 82344 KiB
subtask1_X_05.txt AC 64 ms 82156 KiB
subtask1_X_06.txt AC 78 ms 83128 KiB
subtask1_X_07.txt AC 77 ms 82140 KiB
subtask1_X_08.txt AC 75 ms 82888 KiB