結果

問題 No.3244 Range Multiple of 8 Query
ユーザー kidodesu
提出日時 2025-08-22 22:54:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,529 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 127,300 KB
最終ジャッジ日時 2025-08-22 22:55:04
合計ジャッジ時間 32,415 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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+1)]
for i in range(n+1):
    for j in range(10):
        dp[i][j] = D[j]
    if i == n:
        break
    D[S[i]] = i

inf = 1 << 60
D = [4] * 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)

F = []
G = []
for now in range(1000):
    if D[now] != 4:
        F.append("0" * (3 - len(str(now))) + str(now))
        G.append(D[now])

for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    ans = inf
    for i in range(len(F)):
        now = F[i]
        tmp = G[i]
        s = r
        t0 = dp[r][int(now[-1])]
        if t0 < l:
            continue
        t1 = dp[t0][int(now[-2])]
        if t1 < l:
            continue
        t2 = dp[t1][int(now[-3])]
        if t2 < l:
            continue
        tmp += t1-t2-1 + (t0- t1-1)*2 + (r-t0-1)*3
        ans = min(ans, tmp)
    if ans == inf:
        print(-1)
    else:
        print(ans)
0