Grakn Forces 2020 |
---|
Закончено |
Вам дан неубывающий массив, состоящий из неотрицательных целых чисел $$$a_1, a_2, \ldots, a_n$$$. Также вам дано положительное целое число $$$k$$$.
Вы хотите найти $$$m$$$ неубывающих массивов, состоящих из неотрицательных целых чисел $$$b_1, b_2, \ldots, b_m$$$, таких что:
Найдите минимальное возможное значение $$$m$$$ или сообщите, что ни одного возможного значения $$$m$$$ не существует.
В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 100$$$): количество наборов входных данных.
В первой строке описания каждого набора входных данных находятся два целых числа $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$1 \leq k \leq n$$$).
Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 100$$$, $$$a_n > 0$$$).
Для каждого набора входных данных выведите единственное целое число: минимальное возможное значение $$$m$$$. Если таких $$$m$$$ не существует, выведите $$$-1$$$.
6 4 1 0 0 0 1 3 1 3 3 3 11 3 0 1 2 2 3 3 3 4 4 4 4 5 3 1 2 3 4 5 9 4 2 2 3 5 7 11 13 13 17 10 7 0 1 1 2 3 3 4 5 5 6
-1 1 2 2 2 1
В первом наборе входных данных не существует ни одного возможного значения $$$m$$$, потому что все элементы всех массивов должны будут быть равными $$$0$$$. Но в этом случае невозможно получить $$$a_4 = 1$$$ как сумму нескольких нулей.
Во втором наборе входных данных мы можем взять $$$b_1 = [3, 3, 3]$$$. $$$1$$$ — это минимальное возможное значение $$$m$$$.
В третьем наборе входных данных мы можем взять $$$b_1 = [0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]$$$ и $$$b_2 = [0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2]$$$. Легко заметить, что $$$a_i = b_{1, i} + b_{2, i}$$$ для всех $$$i$$$ и количество различных элементов в каждом из массивов $$$b_1$$$ и $$$b_2$$$ равно $$$3$$$ (что не превосходит $$$3$$$). Можно доказать, что $$$2$$$ — это минимальное возможное значение $$$m$$$.
Название |
---|