Processing math: 100%

Задача 3. Борьба с рутиной

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.

Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в i-й день, целым числом ai.

Для оценки рутинности работы сотрудника будем использовать следующую характеристику. Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней. Для каждого такого отрезка найдём количество различных типов заданий, которые работник выполнял на протяжении этих дней, и просуммируем эти значения. Полученную величину обозначим как Sd и будем называть её d-разнообразием. Чем d-разнообразие выше, тем больше различных типов заданий выполнял сотрудник. Профилем вариативности сотрудника будем называть массив значений [S1,S2,,Sn].

Требуется написать программу, которая по заданной последовательности a1,a2,,an типов выполняемых сотрудником заданий вычисляет его профиль вариативности.

Формат входных данных

В первой строке находится единственное целое число n  — количество последовательных рабочих дней, которые необходимо проанализировать (1n2105).

Во второй строке находится n целых чисел a1,a2,,an  — типы заданий, которое выполнял сотрудник (1ai109).

Формат выходных данных

Выведите n целых чисел: S1,S2,,Sn.

Ограничения

1ai109

1n2105

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
112 1n50, 1ai50первая ошибка
2101n50, 1ai1091первая ошибка
3101n500, 1ai1091,2первая ошибка
4121n5000, 1ai50001первая ошибка
5101n5000, 1ai1091 - 4первая ошибка
616 1n2105, 1ai501первая ошибка
730 1n2105, 1ai1091 - 6первая ошибка

Замечание

Рассмотрим, как вычисляются значения Sd в первом примере.

1-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из одного дня.

Отрезок дней Типы заданий Количество различных
1 - 1 1 1
2 - 2 3 1
3 - 3 2 1
4 - 4 1 1
5 - 5 2 1

Значение 1-разнообразия равно S1=1+1+1+1+1=5.


2-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из двух дней.

Отрезок дней Типы заданий Количество различных
1 - 2 1, 3 2
2 - 3 3, 2 2
3 - 4 2, 1 2
4 - 4 1, 2 2

Значение 2-разнообразия равно S2=2+2+2+2=8.


3-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из трех дней.

Отрезок дней Типы заданий Количество различных
1 - 3 1, 3, 2 3
2 - 4 3, 2, 1 3
3 - 5 2, 1, 2 2

Значение 3-разнообразия равно S3=3+3+2=8.


4-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из четырех дней.

Отрезок дней Типы заданий Количество различных
1 - 4 1, 3, 2, 1 3
2 - 5 3, 2, 1, 2 3

Значение 4-разнообразия равно S4=3+3=6.


5-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из пяти дней.

Отрезок дней Типы заданий Количество различных
1 - 5 1, 3, 2, 1, 2 3

Значение 5-разнообразия равно S5=3.


Примеры тестов

Стандартный вход Стандартный выход
1
5
1 3 2 1 2
5 8 8 6 3 
2
3
10 10 10
3 2 1 

0.064s 0.009s 13