結果

問題 No.3244 Range Multiple of 8 Query
ユーザー ks2m
提出日時 2025-08-22 23:19:37
言語 Java
(openjdk 23)
結果
AC  
実行時間 2,718 ms / 5,000 ms
コード長 3,028 bytes
コンパイル時間 2,546 ms
コンパイル使用メモリ 81,892 KB
実行使用メモリ 86,920 KB
最終ジャッジ日時 2025-08-22 23:20:30
合計ジャッジ時間 49,936 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int q = Integer.parseInt(sa[1]);
		char[] s = br.readLine().toCharArray();

		List<List<Integer>> list = new ArrayList<>();
		for (int i = 0; i < 10; i++) {
			list.add(new ArrayList<>());
		}
		for (int i = 0; i < n; i++) {
			int c = s[i] - '0';
			list.get(c).add(i);
		}
		int[][] pre = new int[10][n + 1];
		for (int i = 0; i < 10; i++) {
			int[] wk = pre[i];
			Arrays.fill(wk, -1);
			List<Integer> list2 = list.get(i);
			list2.add(n);
			for (int j = 1; j < list2.size(); j++) {
				int j1 = list2.get(j - 1);
				int j2 = list2.get(j);
				for (int k = j1 + 1; k <= j2; k++) {
					wk[k] = j1;
				}
			}
		}

		int inf = 1000000000;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
			sa = br.readLine().split(" ");
			int l = Integer.parseInt(sa[0]) - 1;
			int r = Integer.parseInt(sa[1]);
			int ans = inf;
			if (l + 1 == r) {
				if (s[l] == '8') {
					ans = 0;
				}

			} else if (l + 2 == r) {
				int c = (s[l] - '0') * 10 + (s[l + 1] - '0');
				if (c % 8 == 0) {
					ans = 0;
				} else {
					c = (s[l + 1] - '0') * 10 + (s[l] - '0');
					if (c % 8 == 0) {
						ans = 1;
					}
				}

			} else {
				for (int j = 0; j < 1000; j += 8) {
					int val = 0;

					int c1 = j % 10;
					int i1 = pre[c1][r];
					if (i1 < l) {
						continue;
					}
					val += r - 1 - i1;

					int c2 = j / 10 % 10;
					Integer i2 = -1;
					if (c1 == c2) {
						i2 = pre[c2][i1];
						if (i2 < l) {
							continue;
						}
						val += r - 2 - i2;
					} else {
						i2 = pre[c2][r];
						if (i2 < l) {
							continue;
						}
						if (i1 < i2) {
							if (i2 != r - 1) {
								val += r - 1 - i2;
							}
						} else {
							val += r - 2 - i2;
						}
					}

					int c3 = j / 100 % 10;
					if (c2 == c3) {
						int i3 = pre[c3][i2];
						if (i3 < l) {
							continue;
						}
						if (c1 == c3) {
							val += r - 3 - i3;
						} else {
							if (i1 < i3) {
								if (i3 != r - 2) {
									val += r - 2 - i3;
								}
							} else {
								val += r - 3 - i3;
							}
						}
					} else {
						if (c1 == c3) {
							int i3 = pre[c3][i1];
							if (i3 < l) {
								continue;
							}
							if (i2 < i3) {
								if (i3 != r - 2) {
									val += r - 2 - i3;
								}
							} else {
								val += r - 3 - i3;
							}
						} else {
							int i3 = pre[c3][r];
							if (i3 < l) {
								continue;
							}
							val += r - 3 - i3;
							if (i1 < i3) val++;
							if (i2 < i3) val++;
						}
					}
					ans = Math.min(ans, val);
				}
			}
			if (ans == inf) {
				ans = -1;
			}
			sb.append(ans).append('\n');
		}
		System.out.print(sb.toString());
		br.close();
	}
}
0