結果

問題 No.3244 Range Multiple of 8 Query
ユーザー kidodesu
提出日時 2025-08-22 23:17:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,620 bytes
コンパイル時間 1,427 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 139,392 KB
最終ジャッジ日時 2025-08-22 23:18:43
合計ジャッジ時間 34,327 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 18 TLE * 2 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, q = map(int, input().split())
S = input()
S = [int(S[i])%8 for i in range(n)]
D = [-1] * 10
dp = [[-1] * 10 for _ in range(n+2)]
for i in range(n+1):
    for j in range(10):
        dp[i][j] = D[j]
    if i == n:
        break
    D[S[i]] = i

C = set()
inf = 1 << 60
D = [inf] * 1000
from itertools import permutations as P
for now in range(1000):
    if now % 8:
        continue
    a = now
    now = str(now)
    now = "0" * (3 - len(now)) + now
    if "8" in now or "9" in now:
        continue
    D[a] = 0
    for per in P(range(3), 3):
        nxt = ""
        for i in range(3):
            nxt += now[per[i]]
        nxt = int(nxt)
        if per == (1, 0, 2) or per == (0, 2, 1):
            D[nxt] = min(D[nxt], 1)
        elif per == (2, 1, 0):
            D[nxt] = min(D[nxt], 3)
        else:
            D[nxt] = min(D[nxt], 2)
    C.add("".join(sorted(now)))
C = list(C)

for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    ans = inf
    for c in C:
        c = [int(c[i]) for i in range(3)]
        t0 = dp[r][c[0]]
        if c[0] == c[1]:
            t1 = dp[t0][c[1]]
        else:
            t1 = dp[r][c[1]]
        if c[1] == c[2]:
            t2 = dp[t1][c[2]]
        else:
            t2 = dp[r][c[2]]
        if min(t0, t1, t2) < l:
            continue
        A = [t0, t1, t2]
        A.sort()
        idx0, idx1, idx2 = A
        nxt = S[idx0] * 100 + S[idx1] * 10 + S[idx2]
        tmp = D[nxt] + (r-idx2-1)*3 + (idx2-idx1-1)*2 + (idx1-idx0-1)
        ans = min(ans, tmp)
    if ans >= inf:
        print(-1)
    else:
        print(ans)
0