結果

問題 No.3244 Range Multiple of 8 Query
ユーザー kidodesu
提出日時 2025-08-22 23:25:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,003 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 139,024 KB
最終ジャッジ日時 2025-08-22 23:26:40
合計ジャッジ時間 31,831 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

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
    if r - l == 1:
        if S[l] == 0:
            print(0)
        else:
            print(-1)
    elif r - l == 2:
        if not (S[l] * 10 + S[r-1]) % 8:
            print(0)
        elif not (S[r-1] * 10 + S[l]) % 8:
            print(1)
        else:
            print(-1)
    else:
        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