Задача A. Cигнал/шум ≡

Условие

Исследователь улавливает звуковой сигнал с помощью гидролокатора, и желает определить частоту источника звука. Амплитуда звука источника определяется формулой v_i = ⌊ 100 sin(ϕ t)⌋, где ϕ — неизвестная целочисленная частота, t — время в миллисекундах, начиная с 0. ⌊ x⌋ — округление вниз. Гидролокатор улавливал звук в течение N миллисекунд. Принятый локатором сигнал искажён шумом, в результате чего не более 10% от общего количество принятых значений заменены неверными.

Требуется определить частоту источника звука ϕ.

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

Первая строка входных данных содержит целое число N.

Вторая строка содержит N целых чисел v_i — значения звуковых сигналов.

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

Выходные данные должны содержать единственное целое число ϕ.

Ограничения

1 ≤ ϕ  ≤ 100

 − 100 ≤ v_i ≤ 100

10 ≤ N ≤ 100

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

10
-25 -96 -55 65 91 -14 -99 -43 74 85

5

Задача B. Гейм-дизайн ≡

Условие

Компания по разработке настольных игр планирует к выпуску простую игру. Игра ведётся на полоске из N клеток, пронумерованных от 1 до N слева направо. Каждая клетка либо пуста, либо содержит число в диапазоне от 1 до N − 1.

На первом ходу фишка игрока находится на клетке номер 1. Во время ходя игрок кидает кубик, получая равномерно распределённое число в диапазоне от 1 до 6. Игрок двигает фишку вправо на выпавшее количество клеток. Если новая клетка пуста, то фишка остаётся на ней, а если клетка содержит число k, то фишка немедленно перемещается в клетку номер k.

Игра заканчивается, когда игроку выпало число, требующее переместить фишку на последнюю клетку или ещё правее.

Чтобы сбалансировать игру, требуется определить среднюю продолжительность игры, то есть математическое ожидание количества ходов до окончания игры.

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

Первая строка входных данных содержат целое число N.

Вторая строка содержит N целых чисел d_i, где d_i = 0 если ячейка пуста, либо содержит номер ячейки на которую следует перейти при попытке пойти в ячейку i.

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

Выходные данные должны содержать единственное вещественное число с абсолютной ошибкой не более 10^− 3 — математическое ожидание количества ходов.

Ограничения

2 ≤ N ≤ 25, 0 ≤ d_i ≤ N − 1, d₁ = d_N = d_di = 0

Гарантируется, что существует хотя бы одна последовательность ходов, приводящая к окончанию игры.

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

2
0 0

1

3
0 0 0

1.166667

3
0 1 0

1.2