Good Bye 2021: 2022 is NEAR |
---|
Закончено |
Массив $$$a_1, a_2, \ldots, a_n$$$ называется хорошим, если и только если для любого подотрезка $$$1 \leq l \leq r \leq n$$$, выполняется следующее: $$$a_l + a_{l + 1} + \ldots + a_r = \frac{1}{2}(a_l + a_r) \cdot (r - l + 1)$$$.
Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. За одну операцию вы можете заменить один любой элемент массива на любое вещественное число. Определите минимальное число операций, необходимое, чтобы сделать массив хорошим.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$): количество наборов входных данных.
Далее следуют описания $$$t$$$ наборов входных данных, по две строки на набор.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 70$$$): количество чисел в массиве.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \leq a_i \leq 100$$$): изначальный массив.
Для каждого набора входных данных выведите одно целое число: минимальное число элементов, которое нужно заменить, чтобы массив стал хорошим.
5 4 1 2 3 4 4 1 1 2 2 2 0 -1 6 3 -2 4 -1 -4 0 1 -100
0 2 0 3 0
В первом примере массив хороший изначально.
Во втором примере один из возможных хороших массивов — $$$[1, 1, \underline{1}, \underline{1}]$$$ (замененные элементы подчеркнуты).
В третьем примере массив хороший изначальное.
Во четвертом примере один из возможных хороших массивов — $$$[\underline{-2.5}, -2, \underline{-1.5}, -1, \underline{-0.5}, 0]$$$.
Название |
---|