結果

問題 No.3244 Range Multiple of 8 Query
ユーザー ゼット
提出日時 2025-08-24 00:21:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,015 bytes
コンパイル時間 571 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 113,040 KB
最終ジャッジ日時 2025-08-24 00:23:11
合計ジャッジ時間 86,216 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 19 WA * 21
権限があれば一括ダウンロードができます

ソースコード

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
  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