Codeforces Round 876 (Div. 2) |
---|
Закончено |
У вас есть $$$n$$$ разноцветных шаров, расположенных в ряд. Шары покрашены в $$$n$$$ различных цветов, пронумерованных от $$$1$$$ до $$$n$$$. Цвет $$$i$$$-го слева шара равен $$$c_i$$$. Вы хотите переупорядочить шары так, чтобы $$$i$$$-й слева шар имел цвет $$$i$$$. Для этого вы можете использовать $$$k \ge 1$$$ одинаковых шаров цвета $$$0$$$.
Из-за странных свойств шаров их можно переупорядочивать только используя следующие операции:
Вы можете применять эти операции в любом порядке. После того, как вы закончите применять операции, все шары цвета $$$0$$$ магическим образом исчезнут из ряда. После этого в ряду останутся только $$$n$$$ шаров ненулевых цветов.
Какое наименьшее количество монет вам нужно потратить на операции второго типа, чтобы после исчезновения всех шаров нулевого цвета $$$i$$$-й слева шар имел цвет $$$i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$? Можно показать, что при данных ограничениях это всегда можно сделать.
Решите задачу для всех $$$k$$$ от $$$1$$$ до $$$n$$$.
В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 500$$$) — количество шаров в ряду.
Во второй строке заданы $$$n$$$ различных целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le n$$$) — цвета шаров в ряду.
Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$500$$$.
Для каждого набора входных данных выведите $$$n$$$ чисел: $$$i$$$-е ($$$1 \le i \le n$$$) из них должно быть равно наименьшему количеству монет, которого достаточно для требуемого переупорядочивания шаров при $$$k = i$$$.
362 3 1 4 6 531 2 3117 3 4 6 8 9 10 2 5 11 1
3 2 2 2 2 2 0 0 0 10 5 4 4 4 4 4 4 4 4 4
В первом наборе входных данных есть $$$n = 6$$$ шаров. Цвета шаров слева направо равны $$$[\, 2, 3, 1, 4, 6, 5 \,]$$$.
Пусть $$$k = 1$$$. Один из способов переставить шары в требуемом порядке за $$$3$$$ монеты:
$$$[\, 2, 3, 1, 4, 6, 5 \,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, 1, 4, \color{red}{0}, 6, 5 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, 2, 3, \color{blue}{4}, 1, 0, 6, 5 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, \color{blue}{1}, 2, 3, 4, 0, 6, 5 \,]$$$ $$$\xrightarrow{\, 2\,}$$$ $$$[\, 1, 2, 3, 4, 0, 5, \color{blue}{6} \,]$$$
Число над стрелкой обозначает тип операции. Красным выделены шары, вставленные в операциях первого типа, синим — шары, передвинутые в операциях второго типа.
Можно показать, что для $$$k = 1$$$ невозможно расставить шары в правильном порядке, потратив меньше $$$3$$$ монет.
Пусть $$$k = 2$$$. Один из способов переставить шары в требуемом порядке за $$$2$$$ монеты:
$$$[\, 2, 3, 1, 4, 6, 5 \,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, 1, 4, 6, \color{red}{0}, 5\,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, 2, 3, 1, 4, 0, 5, \color{blue}{6}\,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, \color{red}{0}, 1, 4, 0, 5, 6 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, \color{blue}{1}, 2, 3, 0, 4, 0, 5, 6\,]$$$
Эта последовательность операций является корректной и для $$$k$$$, больших $$$2$$$.
Можно показать, что для $$$k$$$ от $$$2$$$ до $$$6$$$ невозможно расставить шары в правильном порядке, потратив меньше $$$2$$$ монет.
Во втором запросе шары уже стоят в правильном порядке, поэтому ответы для всех $$$k$$$ равны $$$0$$$.
Название |
---|