Задача A. Всем поровну ≡

Условие

На день рождения Пети пришли N гостей. Каждый из них принёс n_i конфет. Перед началом торжества Петя решил поделить конфеты поровну между всеми присутствующими, отложив остаток на потом. Сколько конфет достанется каждому?

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

Первая строка входного файла содержит натуральное число N — количество гостей. Вторая строка входного файла содержит N целых чисел — количество конфет, которое принёс каждый гость.

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

Выходной файл должен содержать единственное целое число — количество конфет, доставшихся каждому.

Ограничения

1 ⩽ N ⩽ 100000

0 ⩽ n_i ⩽ 100000

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

3
2 2 4

2

3
1 2 3

1

Задача B. Диаметр окружности ≡

Условие

Пусть задано некоторое растровое изображение размером H × W. Известно, что изображение содержит единственную окружность с диаметром d ∈ N, d mod 2 = 1, при этом окружность была нарисована с использованием Midpoint circle algorithm. Требуется вычислить диаметр d.

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

Входной файл содержит изображение, значением 0 обозначены пиксели принадлежащие фону, значением 1 — окружности. Гарантируется, что изображение содержит все пиксели окружности.

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

Выходной файл должен содержать единственное натуральное число d — диаметр окружности.

Ограничения

1 ⩽ H,W ⩽ 1000

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

0011100
0100010
1000001
1000001
1000001
0100010
0011100

7

Задача C. Интерполяция ≡

Условие

Требуется для некоторой неизвестной функции f:R↦R заданной на равномерной сетке x_i = x₀ + iΔ x,f_i = f(x_i),i = 0,n − 1 получить значения f_j на сетке с меньшим шагом x_j = x₀ + j2Δ x,j = 0,2(n − 1).

Тестирование проводится для одной и той же функции f. Входные данные для второго теста можно скачать здесь.

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

Входной файл содержит n пар вещественных чисел x_i, f_i.

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

Выходной файл должен содержать 2n − 1 вещественных чисел f_j с точностью не менее трёх знаков после запятой.

Ограничения

5 ⩽ n ⩽ 10001

 − 10⁵ ⩽ x ⩽ 10⁵

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

-4 10.464779796751555
-2  8.608842491956457
 0  5.987840056419071
 2  3.0115451750183895
 4  0.12229973341539341

10.4648 9.6549 8.6088 7.3699 5.9878 4.5164 3.0115 1.529 0.1223

Задача D. IOU для предложений ≡

Условие

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

IOU = количество слов встречающихся и в первом и во втором предложенииколичество слов в объединении предложений

Пояснение к первому примеру

Оба предложения содержат слова my, name, is. Объединение этих предложений содержит слова my, name, is, alice, bob. Таким образом, IOU = 35 = 0.6.

Пояснение ко второму примеру

Оба предложения содержат слова my, name, is, bob. Объединение этих предложений содержит слова my (дважды), name (дважды), is (дважды), alice, bob. Таким образом, IOU = 48 = 0.5.

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

Входной файл содержит два предложения.

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

Выходной файл должен содержать единственное вещественное число — IOU предложений с точностью не менее трёх знаков после запятой.

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

my name is alice
my name is bob

0.6

my name is alice my name is bob
my name is bob

0.5

Задача E. Golomb sequence ≡

Условие

Последовательностью Голомба называется последовательность неубывающих натуральных чисел a_n такая, что значение a_n равно количеству повторений числа n в этой последовательности, при этом a₁ = 1, a₂ = 2 и a_n выбирается как минимально возможное число, удовлетворяющее свойству последовательности и a_n ⩾ a_n − 1. Таким образом, первыми элементами последовательности являются

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, …

Общий член последовательности при этом может быть вычислен как

a_n = a(n) = 1 + a(n − a(a(n − 1))),  n > 1 .

Требуется для заданного числа n ∈ N вычислить элемент последовательности a_n.

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

Первая строка входного файла содержит единственное натуральное число n.

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

Выходной файл должен содержать единственное натуральное число a_n.

Ограничения

Задача содержит три группы тестов. Баллы за каждый тест начисляются отдельно.

• 10 тестов, 1 балл за тест, 1 ⩽ n ⩽ 50
• 10 тестов, 1 балл за тест, 51 ⩽ n ⩽ 999
• 5 тестов, 4 балла за тест, 1000 ⩽ n ⩽ 10⁶

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

10

5

50

13