問題一覧 > 通常問題

No.3051 Make All Divisible

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : suisen / テスター : 👑 hamamu 👑 rin204
お気に入りにしたユーザー ProblemId : 11849 / 自分の提出
問題文最終更新日: 2025-01-20 00:25:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 459 (順位表) の他の問題:

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 -1 on $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もしくは右上の雲マークをクリックしてアカウントを作成してください。