Codeforces Round 904 (Div. 2) |
---|
Закончено |
Рассмотрим массив целых чисел $$$b_0, b_1, \ldots, b_{n-1}$$$. Ваша цель — сделать все элементы в нем равными. Для этого вы можете выполнять следующую операцию несколько раз (возможно, ни одного):
Значение $$$f(b)$$$ определяется как пара чисел $$$(cnt, cost)$$$, где $$$cnt$$$ — это наименьшее количество операций, необходимых для того, чтобы сделать все числа массива равными, а $$$cost$$$ — это наибольшее суммарное количество монет, которые можно получить, среди всех возможных вариантов сделать все элементы равными за $$$cnt$$$ операций. Иными словами, в первую очередь нужно минимизировать число операций, во вторую — максимизировать число получаемых монет.
Вам дан массив целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$. Найдите значение $$$f$$$ для всех циклических сдвигов массива $$$a$$$.
Формально, для каждого $$$0 \le i \le n-1$$$ нужно сделать следующее:
Обратите внимание: при фиксированном $$$cnt$$$ нужно максимизировать суммарную стоимость $$$cost$$$, а не ее остаток по модулю $$$(10^9 + 7)$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных для каждого $$$0 \le i \le n-1$$$ выведите значение $$$f$$$ для $$$i$$$-го циклического сдвига массива $$$a$$$: сначала выведите $$$cnt$$$ (наименьшее количество операций), затем $$$cost$$$ (наибольшее суммарное число монет, которое могут принести эти операции) по модулю $$$10^9 + 7$$$.
51131 3 253 2 4 5 186 5 6 4 2 6 2 2410 10 10 10
0 0 3 3 2 5 2 5 7 18 7 16 6 22 5 28 5 28 9 27 9 27 9 27 9 27 11 23 9 27 9 27 13 19 0 0 0 0 0 0 0 0
В первом наборе входных данных есть всего один циклический сдвиг, задающийся массивом $$$[1]$$$, и в нем все элементы уже равны.
Во втором наборе входных данных нужно найти ответ на трех массивах:
Рассмотрим детально случай $$$[2, 1, 3]$$$. Чтобы сделать все элементы равными, на первой операции можно выбрать $$$l = 1$$$ и $$$r = 1$$$, получив массив $$$[2, 2, 3]$$$. На второй операции можно выбрать $$$l = 0$$$ и $$$r = 1$$$, получив массив $$$[3, 3, 3]$$$. Мы использовали $$$2$$$ операции, суммарная стоимость которых равна $$$1^2 + 2^2 = 5$$$.
Название |
---|