結果

問題 No.3244 Range Multiple of 8 Query
ユーザー ks2m
提出日時 2025-08-22 23:11:22
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 3,022 bytes
コンパイル時間 2,663 ms
コンパイル使用メモリ 81,752 KB
実行使用メモリ 84,000 KB
最終ジャッジ日時 2025-08-22 23:12:30
合計ジャッジ時間 25,024 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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 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 = lower(list.get(c1), r);
					if (i1 < l) {
						continue;
					}
					val += r - 1 - i1;

					int c2 = j / 10 % 10;
					Integer i2 = -1;
					if (c1 == c2) {
						i2 = lower(list.get(c2), i1);
						if (i2 < l) {
							continue;
						}
						val += r - 2 - i2;
					} else {
						i2 = lower(list.get(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 = lower(list.get(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 = lower(list.get(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 = lower(list.get(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();
	}

	static int lower(List<Integer> list, int val) {
		int ng = list.size();
		int ok = -1;
		while (Math.abs(ok - ng) > 1) {
			int mid = (ok + ng) / 2;
			if (list.get(mid) < val) {
				ok = mid;
			} else {
				ng = mid;
			}
		}
		if (ok == -1) {
			return -1;
		}
		return list.get(ok);
	}
}
0