結果
問題 |
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 |
ソースコード
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)