| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 15 | 9 | 9 | 64.286% |
Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.
Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в i-й день, целым числом ai.
Для оценки рутинности работы сотрудника будем использовать следующую характеристику. Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней. Для каждого такого отрезка найдём количество различных типов заданий, которые работник выполнял на протяжении этих дней, и просуммируем эти значения. Полученную величину обозначим как Sd и будем называть её d-разнообразием. Чем d-разнообразие выше, тем больше различных типов заданий выполнял сотрудник. Профилем вариативности сотрудника будем называть массив значений [S1, S2, . . . , Sn].
Требуется написать программу, которая по заданной последовательности a1, a2, . . . , an типов выполняемых сотрудником заданий вычисляет его профиль вариативности.
В первой строке находится единственное целое число n — количество последовательных рабочих дней, которые необходимо проанализировать (1 ≤ n ≤ 2 · 105).
Во второй строке находится n целых чисел a1, a2, . . . , an — типы заданий, которое выполнял сотрудник (1 ≤ ai ≤ 109).
Выведите n целых чисел: S1, S2, . . . , Sn.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | 1 ≤ n ≤ 50 1 ≤ ai ≤ 50 |
| 2 | 10 | 1 ≤ n ≤ 50 1 ≤ ai ≤ 109 |
| 3 | 10 | 1 ≤ n ≤ 500 1 ≤ ai ≤ 109 |
| 4 | 12 | 1 ≤ n ≤ 5000 1 ≤ ai ≤ 5000 |
| 5 | 10 | 1 ≤ n ≤ 5000 1 ≤ ai ≤ 109 |
| 6 | 16 | 1 ≤ n ≤ 2·105 1 ≤ ai ≤ 50 |
| 7 | 30 | 1 ≤ n ≤ 2·105 1 ≤ ai ≤ 109 |
5 1 3 2 1 2
5 8 8 6 3
3 10 10 10
3 2 1
Рассмотрим, как вычисляются значения 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 - 5 | 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.
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2020 3번