結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー kidodesu
提出日時 2025-08-22 22:52:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,534 bytes
コンパイル時間 359 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 135,060 KB
最終ジャッジ日時 2025-08-22 22:52:37
合計ジャッジ時間 31,522 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 18 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+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

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 = 1 << 30
    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 == 1 << 30:
        print(-1)
    else:
        print(ans)
0