No.3051 Make All Divisible
Problem Statement
You are given a sequence of non-negative integers $A = (A_1, A_2, \ldots, A_n)$ of length $n$ and a positive integer $k$ not greater than $n$.
You may perform the following operation on $A$ any number of times, possibly $0$ times.
- Choose integers $i _ 1, i _ 2, \ldots, i _ k$ such that $1\leq i _ 1\lt i _ 2\lt \cdots \lt i _ k \leq n$, and decrease each of $A_{i _ 1}, A_{i _ 2}, \ldots, A_{i _ k}$ by $1$.
Your goal is to make the sequence $A$ satisfy all of the following conditions.
- $A _ 1, A _ 2, \ldots, A _ n$ are all multiples of $k$.
- $A _ 1, A _ 2, \ldots, A _ n$ are all at least $0$.
Determine whether the goal is achievable, and if it is, find the minimum number of operations needed to achieve the goal.
Each file contains $T$ test cases in 1 file; solve the above problem for all of them.
Input
The input is given from Standard Input in the following format.
$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$
$\mathrm{testcase}_i$ represents the $i$-th test case and is given in the following format.
$n$ $k$ $A_1$ $A_2$ $\cdots$ $A_n$
- All input values are integers.
- $1\leq T\leq 2000$
- $1\leq k\leq n\leq 2000$
- $0\leq A_i\leq 10 ^ {15}$
- The sum of $n$ over all test cases is at most $2000$.
Output
On the $i$-th line, print the answer for the $i$-th test case. Print the answer for each test case in the following format.
- If the goal is not achievable, print
-1on $1$ line. - If the goal is achievable, print the minimum number of operations needed to achieve the goal on $1$ line.
Print a newline after the output for the $T$-th test case as well.
Sample
Sample 1
Input
4 3 2 1 2 7 5 4 1 2 3 4 5 5 3 1 2 3 4 5 7 3 3 6 0 9 3 3 0
Output
1 -1 2 0
-
For the 1st test case:
This input represents $n=3$, $k=2$, $A=(1, 2, 7)$.
Since $A _ 1, A _ 3$ are not multiples of $2$, the conditions are not satisfied initially.
Performing the operation with $(i _ 1, i _ 2) = (1, 3)$ makes $A=(0, 2, 6)$. Now $A _ 1, A _ 2, A _ 3$ are all multiples of $2$ and all at least $0$, so the conditions are satisfied.
Therefore, the minimum number of operations needed to achieve the goal is $1$.
-
For the 2nd test case:
It can be proved that the goal cannot be achieved no matter how you perform the operations, so print
-1. -
For the 4th test case:
The goal is already achieved without performing any operations.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu