結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー むつある
提出日時 2025-08-23 02:18:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,633 ms / 5,000 ms
コード長 993 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 82,116 KB
実行使用メモリ 153,236 KB
最終ジャッジ日時 2025-08-23 02:19:38
合計ジャッジ時間 66,107 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,Q=map(int,input().split())
s=input()

x=[[[-1]*3 for _ in range(10)]]
for v,i in enumerate(s):
  now=x[-1][:]
  now[int(i)]=now[int(i)][1:]+[v]
  x.append(now)

q=[]
  
for i in range(1000):
  if i%8:
    continue
  q.append([i//100,(i%100)//10,i%10])
  
inf=10**18

def calc(a,b,c,r):
  ans=0
  ans+=r-c
  if b>c:
    b-=1
  if a>c:
    a-=1
  ans+=r-b-1
  if a>b:
    a-=1
  ans+=r-a-2
  return ans
  
for _ in range(Q):
  l,r=map(int,input().split())
  ans=inf
  
  if l==r:
    if s[r-1]=='8':
      print(0)
    else:
      print(-1)
    continue
  if l+1==r:
    if int(s[l-1:r])%8==0:
      print(0)
    elif (int(s[r-1])*10+int(s[l-1]))%8==0:
      print(1)
    else:
      print(-1)
    continue
  
  p=x[r]
  for a,b,c in q:
    cnt=[0]*10
    C=p[c][-cnt[c]-1]
    cnt[c]+=1
    B=p[b][-cnt[b]-1]
    cnt[b]+=1
    A=p[a][-cnt[a]-1]
    cnt[a]+=1
    if min(A,B,C)<l-1:
      continue
    
    ans=min(ans,calc(A,B,C,r-1))
    
  if ans==inf:
    print(-1)
  else:
    print(ans)
0