結果

問題 No.3244 Range Multiple of 8 Query
ユーザー むつある
提出日時 2025-08-23 02:15:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 993 bytes
コンパイル時間 558 ms
コンパイル使用メモリ 82,612 KB
実行使用メモリ 153,108 KB
最終ジャッジ日時 2025-08-23 02:16:46
合計ジャッジ時間 56,716 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 27 WA * 13
権限があれば一括ダウンロードができます

ソースコード

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