Это сложная версия задачи. Единственное отличие — в этой версии задачи \(0 \leq k \leq 20\).
Дан массив \(a_1, a_2, \ldots, a_n\) из \(n\) положительных целых чисел. Необходимо разбить его на наименьшее количество непрерывных отрезков так, чтобы ни на каком отрезке не было двух чисел (на разных позициях), произведение которых является полным квадратом.
При этом до разбиения разрешается сделать не более \(k\) раз следующую операцию: выбрать любое число в массиве и заменить его значение на произвольное целое положительное число.
Какое наименьшее количество непрерывных отрезков нужно использовать, если сделать изменения оптимально?
Выходные данные
Для каждого набора входных данных выведите одно число — ответ на задачу.
Примечание
В первом наборе входных данных можно сначала изменить массив следующим образом: \([\underline{3}, 6, 2, 4, \underline{5}]\) (изменённые числа подчёркнуты). После этого его не нужно разделять, поэтому ответ \(1\).
Во втором наборе входных данных можно сначала изменить массив следующим образом: \([6, 2, \underline{3}, 8, 9, \underline{5}, 3, 6, \underline{10}, \underline{11}, 7]\). После этого такое разбиение будет оптимальным:
- \([6, 2, 3]\)
- \([8, 9, 5, 3, 6, 10, 11, 7]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 2
18 6 2 4 1
11 4
6 2 2 8 9 1 3 6 3 9 7
1 0
1
|
1
2
1
|