Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Борьба с рутиной

(Время: 2 сек. Память: 16 Мб Сложность: 52%)

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

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

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

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

Входные данные

В первой строке входного файла INPUT.TXT находится единственное целое число n — количество последовательных рабочих дней, которые необходимо проанализировать (1 ≤ n ≤ 2×105).

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

Выходные данные

В выходной файл OUTPUT.TXT выведите n целых чисел: S1, S2, ... , Sn.

Примеры

INPUT.TXTOUTPUT.TXT
15
1 3 2 1 2
5 8 8 6 3
23
10 10 10
3 2 1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Разность квадратов
 B. Превышение скорости
 C. Борьба с рутиной
 D. Олимпиада для роботов
 E. Максимальное произведение
 F. Планировка участка
 G. Банкомат
 H. Плакаты

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru