Зимний личный чемпионат ИжГТУ по программированию 2023
A. Hello, world!
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Выведите первые $$$n$$$ символов строки «Hello, world!».

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

Первая строка содержит одно целое число $$$k$$$ ($$$1 \leqslant k \leqslant 100\,000$$$).

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

Выведите одну строку — первые $$$n$$$ символов фразы «Hello, world!», где

$$$$$$ n = \left[ \int\limits_{-6}^{k-7} 2.0196 \cos(0.483322 x) - 2.080042 \cos(0.966644 x) + 2.186573 \cos(1.449966 x)~ - \right.$$$$$$ $$$$$$ \left.-~ 2.34912\cos(1.933288 x) + 2.584564\cos(2.41661 x) - 2.921231\cos(2.899932 x) dx + \int\limits_{-k}^{k}{ x^4 \sin(a x) e^{x^2} dx} + b \right]$$$$$$

$$$a$$$ — значение в точке $$$k$$$ функции $$$y(x)$$$, которая является решением дифференциального уравнения $$$$$$y' ' '(x) + k y' '(x) - 10 y'(x) + 7 y(x) = e^{kx} cos(\pi k)$$$$$$ и которая удовлетворяет условиям:

$$$$$$y(0) = k$$$$$$ $$$$$$y'(0) = 2 k$$$$$$ $$$$$$y' '(0) = 1$$$$$$

$$$b$$$ — наименьший корень уравнения $$$x^2 - (1 + k)x + k = 0$$$.

Операция $$$[x]$$$ означает округления числа $$$x$$$ до ближайшего целого.

Примеры
Входные данные
13
Выходные данные
Hello, world!
Входные данные
100000
Выходные данные
Hell

B. Шифр
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим некоторый алгоритм шифрования последовательности, состоящей только из цифр от $$$0$$$ до $$$9$$$. Алгоритм состоит из двух этапов.

Каждый шаг первого этапа алгоритма состоит из взятия очередных $$$10$$$ элементов последовательности (или всех оставшихся, если их меньше $$$10$$$), перестановки цифр случайным образом и приписывания перед каждой цифрой ее порядковый номер в $$$0$$$-индексации в этой десятке.

На втором этапе заменяем каждую цифру $$$i$$$ на $$$a_i$$$.

Рассмотрим следующий пример. Пусть $$$a = \{7, 6, 3, 5, 1, 2, 0, 9, 8, 4\}$$$, а сама последовательность пусть выглядит так: $$$05908535645376$$$.

Возьмём первые $$$10$$$ цифр и переставим их случайным образом: $$$6549055083$$$, допишем перед каждой цифрой номер её позиции в начальной последовательности: $$$86159429005575304863$$$. Возьмём оставшиеся $$$4$$$ цифры, переставим их: $$$3675$$$. Допишем их номера — $$$13362705$$$. Получили последовательность $$$8615942900557530486313362705$$$.

Теперь заменим каждую цифру, согласно массиву $$$a$$$. И получаем итоговую последовательность: $$$8062413477229257180565503972$$$.

Вам задана зашифрованная последовательность и числа $$$a_0$$$, $$$a_1$$$, ..., $$$a_9$$$. Расшифруйте её.

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

Первая строка содержит $$$10$$$ различных целых чисел от $$$0$$$ до $$$9$$$ — значения $$$a_0$$$, $$$a_1$$$, ..., $$$a_9$$$. Вторая строка содержит последовательность цифр длиной от $$$2$$$ до $$$100\,000$$$ — последовательность, которую надо расшифровать.

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

Выведите последовательность цифр — расшифрованную последовательность.

Пример
Входные данные
7 6 3 5 1 2 0 9 8 4
8062413477229257180565503972
Выходные данные
05908535645376

C. Окружности
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

На плоскости находятся $$$n$$$ ($$$1 \leqslant n \leqslant 2\, 000$$$) окружностей с целочисленными координатами и целочисленными положительными радиусами, лежащие полностью внутри квадрата с вершинами $$$(0, 0)-(20, 0)-(20, 20)-(0, 20)$$$. Имея возможность узнать количество окружностей, содержащих выбранную точку внутри или на границе, определите, сколько всего окружностей лежат внутри квадрата.

Протокол взаимодействия

Программа участника должна выводить в стандартный поток вывода координаты двух точек $$$x$$$ и $$$y$$$ с точностью до $$$5$$$ знаков после запятой ($$$0 \leqslant x, y \leqslant 20$$$). После этого программа жюри выведет одно целое число — количество окружностей, содержащих данную точку.

Когда программа участника найдет ответ, она должна вывести слово «Done» и через пробел ответ на задачу и затем завершиться.

Количество запросов не должно превышать $$$5\, 000$$$.

Пример
Входные данные

2

2

2

2

2

1

1

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

1.0 0.0

0.0 1.0

2.0 1.0

1.0 2.0

5.0 5.0

5.0 7.0

5.1 6.0

Done 3
Примечание

В примере две окружности имеют центр в $$$(1, 1)$$$ и радиус $$$1$$$, и ещё одна имеет центр в $$$(5, 6)$$$ и радиус $$$2$$$.

D. Пляж
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Пляж представляет собой территорию, разбитую на сектора $$$1$$$ на $$$1$$$ метр, в центре которого располагается квадратное озеро, размером $$$n \times n$$$ метров. Каждый новый отдыхающий, придя на пляж, выбирает себе наиближайший к озеру свободный сектор и занимает его. Расстояние между секторами с координатами $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ равно $$$|x_1 - x_2| + |y_1 - y_2|$$$. Расстояние от отдыхающего до озера равно минимальному расстоянию между его сектором и секторами, занятыми озером. Найдите сумму расстояний от всех отдыхающих до озера.

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

Единственная строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leqslant n, k \leqslant 10^9$$$) — размер озера и количество отдыхающих соответственно.

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

Выведите одно целое число — сумму расстояний.

Пример
Входные данные
2 6
Выходные данные
6

E. Квадраты
ограничение по времени на тест
0.25 секунд
ограничение по памяти на тест
4 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на нестандартное ограничение по памяти в этой задаче.

Дана таблица размера $$$n \times m$$$, каждая ячейка которой покрашена либо в чёрный, либо в белый цвет. Найдите количество квадратов, состоящих полностью из чёрных ячеек. Размеры квадратов могут быть любыми.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leqslant n, m \leqslant 3\, 000$$$) — количество строк и столбцов таблицы соответственно. Далее следуют $$$n$$$ строк содержащие по $$$m$$$ символов «#» (чёрный цвет) и «.» (белый цвет).

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

Выведите одно целое число — количество квадратов, состоящих полностью из чёрных ячеек.

Пример
Входные данные
3 3
#.#
.##
###
Выходные данные
8

F. Забор
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Необходимо с помощью забора огородить выпуклый участок максимальной площади. Правила построения забора следующие. Разрешается выстраивать непрерывный замкнутый забор из отрезков длины $$$1$$$ и отрезков длины $$$\sqrt{2}$$$, соединенных концами между собой, при этом, в фиксированной декартовой системе координат $$$Oxy$$$. Необходимо использовать ровно $$$n_1$$$ единичных отрезков, параллельных оси $$$x$$$, ровно $$$n_2$$$ единичных отрезков параллельных оси $$$y$$$, ровно $$$n_3$$$ отрезков длины $$$\sqrt{2}$$$ образующих угол в $$$45$$$ градусов с положительной полуосью $$$Ox$$$, ровно $$$n_4$$$ отрезков длины $$$\sqrt{2}$$$ образующих угол в $$$135$$$ градусов с положительной полуосью $$$Ox$$$.

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

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

Единственная строка содержит четыре целых числа $$$n_1$$$, $$$n_2$$$, $$$n_3$$$ и $$$n_4$$$ ($$$1 \leqslant n_i \leqslant 100$$$)

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

Если забора, удовлетворяющего условиям задачи, нет, то выведите одну строку «impossible».

В противном случае выведите ответ в виде строки из четырех цифр ($$$1$$$ — горизонтальный отрезок, $$$2$$$ — вертикальный, $$$3$$$ — диагональный под углом $$$45$$$ градусов, $$$4$$$ — диагональный под углом $$$135$$$ градусов), соответствующих обходу забора по часовой стрелке, начиная с любого отрезка, из которых составлен забор. Если ответов несколько — выведите любой.

Примеры
Входные данные
5 7 1 4
Выходные данные
11144222311442222
Входные данные
5 7 1 5
Выходные данные
impossible

G. Камень, ножницы, бумага
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

$$$n$$$ игроков играют в игру «Камень, ножницы, бумага» (сокращенно «к, н, б»).

Каждый из игроков независимо от других и с равной вероятностью показывает на пальцах один из символов: «к», «н», «б». Если все игроки показали одинаковый символ или все три символа были показаны, то считается, что произошла «ничья». Если показаны два символа, то играющие разбиваются на две группы: победителей и проигравших. При этом камень сильнее ножниц, ножницы сильнее бумаги, бумага сильнее камня. После каждой не «ничейной» игры считается, что каждый игрок из группы победителей «сильнее» каждого игрока из группы проигравших. Победители в каждой игре продолжают играть между собой, а проигравшие также продолжают играть между собой. Игры победителей и проигравших проходят одновременно и независимо.

Каждая игра длится ровно одну секунду, а весь матч, состоящий из серии игр, длится до полного выяснения относительно всех игроков их «силы» относительно друг друга. Продолжительность матча — количество секунд от начала матча до конца последней игры. Задача: найти математическое ожидание продолжительности матча между $$$n$$$ игроками.

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

Единственная строка содержит одно целое число $$$n$$$ ($$$2 \leqslant n \leqslant 25$$$) — количество игроков.

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

Выведите одно вещественное число — ожидаемая продолжительность матча в секундах. Ответ должен отличаться от правильного не более чем на $$$10^{-4}$$$ по абсолютной или относительной погрешности.

Примеры
Входные данные
2
Выходные данные
1.500000
Входные данные
4
Выходные данные
4.446429

H. Сбалансированные деревья
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

Более подробно, каждое дерево можно представить в виде скобочной последовательности. Для этого определим функцию $$$f$$$ следующим образом:

  • если $$$x$$$ — лист, то $$$f(x) = ()$$$;
  • иначе $$$f(x) = (f(\texttt{сын 1}) f(\texttt{сын 2}) ... f(\texttt{сын n}))$$$.

Значение функции $$$f$$$ от корня и даст соответствующую скобочную последовательность.

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

Единственная строка содержит одно целое число $$$n$$$ ($$$1 \leqslant n \leqslant 500$$$) — количество вершин в дереве.

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

Выведите одно целое число — количество сбалансированных деревьев из $$$n$$$ вершин, взятое по модулю $$$10^9+7$$$.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
2
Выходные данные
1
Входные данные
3
Выходные данные
2
Входные данные
4
Выходные данные
3
Входные данные
5
Выходные данные
5
Входные данные
6
Выходные данные
8

I. WA 132
ограничение по времени на тест
0.25 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Команда участвует в соревновании по программированию и решают очередную задачу, про которую известно:

  1. в задаче $$$n$$$ тестов;
  2. каждый тест допускает ровно $$$k$$$ возможных ответов, но только один из них правильный;
  3. входные данные тестов содержат их порядковый номер, который может быть считан программой участника;
  4. в случае неуспешной попытки, участникам сообщается номер первого теста, на котором программа выдала неправильный ответ;
  5. в условии приведен ответ на первый тест.

Команда пытается сдать задачу, опираясь только на информацию, приведенную в списке выше, при этом она не делает попыток, про которые заведомо знает, что она неправильная.

За какое максимальное количество попыток команда может сдать задачу в наихудшем случае?

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

Единственная строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leqslant n, k \leqslant 132$$$) — количество тестов и количество вариантов ответа соответственно.

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

Выведите одно целое число — количество попыток в наихудшем случае.

Пример
Входные данные
132 2
Выходные данные
132

J. Плоские фигуры
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дан выпуклый многоугольник, определите какой плоской фигурой он является.

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

Первая строка содержит одно целое число $$$n$$$ ($$$3 \leqslant n \leqslant 4$$$) — количество вершин многоугольника. Далее следуют $$$n$$$ строк, содержащие по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \leqslant x_i, y_i \leqslant 100$$$) — координаты $$$i$$$-й вершины. Вершины заданы в порядке обхода по или против часовой стрелки. Никакие $$$3$$$ точки не лежат на одной прямой.

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

Выведите одно целое число — номер фигуры из списка:

  1. остроугольный треугольник;
  2. прямоугольный треугольник;
  3. тупоугольный треугольник;
  4. параллелограмм (но не ромб и не прямоугольник);
  5. трапеция;
  6. ромб (но не квадрат);
  7. прямоугольник (но не квадрат);
  8. квадрат.

Гарантируется, что будут даны только те фигуры, которые перечислены в этом списке.

Примеры
Входные данные
3
0 0
1 0
1 1
Выходные данные
2
Входные данные
4
0 0
5 0
5 5
0 5
Выходные данные
8
Входные данные
4
0 0
10 0
8 10
2 10
Выходные данные
5

K. Пора домой!
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Группа студентов задержалась в деканате и очень хочет идти домой. Для этого они хотят составить план, как дойти до аудитории со своими вещами, а затем на улицу. Но так как они слишком сильно устали, они хотят, чтобы этот план был как можно короче.

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

<место 1> -> <место 2> -> <место 3> -> ... -> <место n>

Среди всех планов найдите такой, что

  1. для каждого i от $$$1$$$ до $$$n-1$$$ возможно непостредствено перейти из <место i> в <место i + 1>;
  2. строка не содержит ведущих и концевых пробелов;
  3. каждая стрелка окружена ровно одним пробелом;
  4. название деканата — «deans_office»;
  5. название улицы — «street»;
  6. план содержит строки «deans_office», «street» и название аудитории с вещами ровно один раз;
  7. план начинается со строки «deans_office» и заканчивается строкой «street»;
  8. количество символов в строке минимально возможно.
Входные данные

Первая строка входного файла содержит одну строку — название аудитории с вещами. Оно отличается от названия деканата и улицы.

Далее следуют строки в формате: «<место 1> - <место 2>», означающих, что можно попасть из «места $$$1$$$» в «место $$$2$$$» и наоборот. Количество строк не превосходит $$$101$$$. Названия состоят из строчных латинских букв и знака подчеркивания. Их длина не меньше $$$1$$$ и не больше $$$30$$$.

Гарантируется, что ответ всегда существует.

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

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

Пример
Входные данные
312_2
deans_office - floor_3
floor_3 - 311
floor_3 - 312
floor_3 - 313
floor_3 - 314
floor_3 - 315
floor_3 - 316
floor_3 - 317
floor_3 - 320
floor_3 - 321
floor_3 - 322
floor_3 - 323
floor_3 - 324
floor_3 - 325
312 - 312_1
312 - 312_2
312 - 312_3
312 - 312_4
floor_3 - floor_2
floor_2 - floor_1
floor_1 - floor_0
floor_0 - street
Выходные данные
deans_office -> floor_3 -> 312 -> 312_2 -> 312 -> floor_3 -> floor_2 -> floor_1 -> floor_0 -> street