No.3244 Range Multiple of 8 Query
タグ : / 解いたユーザー数 54
作問者 : 👑
hamamu
ygussany
Problem Statement
For a string $X$ of length $M$, we define an operation as follows.
- Operation: Choose $1$ integer $i$ satisfying $1 \leq i \leq M - 1$. Swap the $i$-th character and the $i+1$-th character of $X$.
For a string $T$ consisting of digits from $1$ to $9$, we define $f(T)$ as follows.
- When you may perform the operation on $T$ any number of times, $0$ or more, the minimum number of operations required to make $T$, viewed as an integer in decimal notation, a multiple of $8$. If this is impossible no matter how the operations are performed, let $f(T) = -1$.
You are given a string $S$ of length $N$ consisting only of digits from $1$ to $9$.
You are given $Q$ queries as described below. Answer each of them.
- Query $i$: You are given a pair of integers $(l_i, r_i)$ satisfying $1 \leq l_i \leq r_i \leq N$. Let $S[l_i, r_i]$ be the substring of $S$ consisting of the $l_i$-th through $r_i$-th characters. Find $f(S[l_i, r_i])$.
Constraints
- $N, Q, l_i, r_i$ are integers.
- $S$ is a string of length $N$ consisting of digits from $1$ to $9$.
- $1 \leq N \leq 2.88 \times 10^5$
- $1 \leq Q \leq 2.88 \times 10^5$
- $1 \leq l_i \leq r_i \leq N$
Input
The input is given from Standard Input in the following format.
$N$ $Q$ $S$ $l_1$ $r_1$ $l_2$ $r_2$ $\vdots$ $l_Q$ $r_Q$
Output
Print $Q$ lines. On the $i \ (1 \leq i \leq Q)$-th line, print the answer to the $i$-th query.
Sample
Sample 1
Input
15 4 123456789111141 6 9 3 6 10 13 8 15
Output
3 0 -1 7
In the $1$-st query, $S[6, 9] = 6789$. Let this be $T$. By performing operations as follows, the value of $T$ viewed as an integer in decimal notation becomes a multiple of $8$ with $3$ operations.
- Choose $i = 1$. Swap the $1$-st and $2$-nd characters of $T$. It becomes $T = 7689$.
- Choose $i = 3$. Swap the $3$-rd and $4$-th characters of $T$. It becomes $T = 7698$.
- Choose $i = 2$. Swap the $2$-nd and $3$-rd characters of $T$. It becomes $T = 7968$.
Since $7968 = 996 \times 8$, $7968$ is a multiple of $8$. The value of $T$ viewed as an integer in decimal notation cannot be made a multiple of $8$ with $2$ or fewer operations, so the answer is $3$.
In the $2$-nd query, $S[3, 6] = 3456$. Since $432 \times 8 = 3456$, the value of $S[3, 6]$ viewed as an integer in decimal notation is a multiple of $8$ from the start, without performing even $1$ operation.
In the $3$-rd query, $S[10, 13] = 1111$. No matter how operations are performed, the value of $S[10, 13]$ viewed as an integer in decimal notation cannot be made a multiple of $8$, so print $-1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。