結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー ゼット
提出日時 2025-08-24 00:23:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,855 ms / 5,000 ms
コード長 1,258 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 113,328 KB
最終ジャッジ日時 2025-08-24 00:25:15
合計ジャッジ時間 89,998 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,Q=map(int,input().split())
S=input()
G=[[] for i in range(10)]
v=[[0]*N for i in range(10)]
for i in range(N):
  x=int(S[i])
  G[x].append(i)
  for y in range(10):
    if y==x:
      v[y][i]=v[y][i-1]+1
    else:
      v[y][i]=v[y][i-1]
M=10**10
for _ in range(Q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  if l==r:
    if S[r]=='8':
      print(0)
    else:
      print(-1)
    continue
  if r==l+1:
    c=int(S[l:r+1])
    d=int(S[r]+S[l])
    if c%8==0:
      print(0)
    elif d%8==0:
      print(1)
    else:
      print(-1)
    continue
    
  h=[[-M]*3 for i in range(10)]
  for x in range(10):
    pos=v[x][r]
    for e in range(pos-1,pos-4,-1):
      if e<0:
        break
      t=G[x][e]
      if t>=l:
        h[x][(pos-1-e)]=t
  result=M
  for y in range(13,125):
    z=str(8*y)
    if '0' in z:
      continue
    ans=0
    a,b,c=int(z[2]),int(z[1]),int(z[0])
    ans+=r-h[a][0]
    pos1=h[a][0]
    k=0
    if b==a:
      k+=1
    ans+=r-1-h[b][k]
    pos2=h[b][k]
    k=0
    if c==a:
      k+=1
    if c==b:
      k+=1
    ans+=r-2-h[c][k]
    pos3=h[c][k]
    if pos1<pos2:
      ans+=1
    if pos1<pos3:
      ans+=1
    if pos2<pos3:
      ans+=1
    result=min(result,ans)
  if result<M//10:
    print(result)
  else:
    print(-1)
0