Задачи муниципального этапа олимпиады школьников по информатике 2015

Наручные часы на электронных чернилах могут показывать текущее время в нескольких разных формах. Одна из форм — это имитация механических часов со стрелками. Циферблат часов разделен на 12 больших часовых делений, а каждое из них — на 5 малых делений. Угол между малыми делениями на циферблате равен 60. Для экономии энергии перерисовка изображения происходит один раз в минуту, когда необходимо переместить минутную стрелку. Часовая стрелка также движется дискретно, перемещаясь через каждые 12 минут на одно малое деление. Таким образом в 12:35 часовая стрелка будет указывать на 2-е малое деление справа от 12 часов, а минутная будет указывать на 7 часов (см. рис). Угол между стрелками в этот момент равен 1620. В 12:36 часовая стрелка переместится на 3-е малое деление после 12 часов, а минутная — на следующее малое деление после 7 часов. Угол между стрелками часов при этом не изменится.

Напишите программу, которая вычисляет величину "внутреннего" (меньшего) угла между часовой и минутной стрелкой в заданный момент времени.

Первая строка ввода содержит два целых числа, разделенных одним пробелом — время на часах, часы `H` и минуты `M` (`1\ ≤\ H\ ≤\ 12`, `0\ ≤\ M\ ≤\ 59`).

Вывести одно целое число в диапазоне от 0 до 180 — величину угла между стрелками в градусах.

12 35

162

`1\ ≤\ H\ ≤\ 12`, `M\ =\ 0`.

В этой подзадаче 12 тестов, каждый тест оценивается в 2 балла. Тесты выполняются в порядке возрастания `H`. Баллы за каждый тест начисляются независимо.

`H\ =\ 12`, `0\ ≤\ M\ ≤\ 59`.

В этой подзадаче 12 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

`1\ ≤\ H\ ≤\ 12`, `0\ ≤\ M\ ≤\ 59`.

В этой подзадаче 10 тестов, каждый тест оценивается в 4 балла. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.

Реализуйте на одном из языков программирования алгоритм, представленный на схеме. Выражение `S\ mod\ K` означает вычисление остатка от деления `S` на `K`.

В первой строке ввода содержится целое число `N` (`1\ ≤\ N\ ≤\ 100`). Далее следует `N` строк, содержащих по одному целому числу в диапазоне от 1 до 1000.

Вывести сообщение Yes или No как указано в алгоритме.

3
2
1
3

Yes

3
1
2
3

No

В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте.

Последовательность натуральных чисел от 1 до `N` нужно разбить на две части от 1 до `K` и от `K+1` до `N` так, чтобы абсолютное значение разности суммы чисел в первой и второй части последовательности было как можно меньше. То есть нужно найти такое `K`, что значение выражения `|\ sum_{i=1}^K\ i\ -\ sum_{i=K+1}^N\ i\ |` минимально. Например, для последовательности чисел от 1 до 4 разбиение будет минимальным для `K=3`, так как `|\ (1+2+3)-(4)\ |\ =\ 2`, что меньше значения разности для `K=1` равного `|\ (1)-(2+3+4)\ |\ =\ 8` и для `K=2` равного `|\ (1+2)-(3+4)\ |\ =\ 4`.

Напишите программу, которая для заданного `N` находит минимальное разбиение.

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^9`).

Вывести одно целое число `K`. Если существует несколько вариантов разбиения, то вывести меньшее из возможных `K`.

4

3

В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

В этой подзадаче 10 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

В этой подзадаче 5 тестов, каждый тест оценивается в 4 балла. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки для всех подзадач (без разделения на отдельные тесты).

В MMORPG "Космические торговцы online" скорость перемещения игрока между звёздами ограничена одним парсеком в секунду. С такой скоростью можно быстро добраться до ближайших звёзд, но на путешествие с одного края галактики до другого может потребоваться несколько часов. Для ускорения таких долгих путешествий создатели игры сделали несколько "кротовых нор" — туннелей, соединяющих две точки в пространстве, которые позволяют мгновенно перемещаться между этими точками туда и обратно.

Напишите программу, которая вычисляет минимальное время путешествия, используя информацию о "кротовых норах".

В первой строке ввода содержится целое число `N` (`1\ ≤\ N\ ≤\ 100`). Далее следует строка, содержащая 6 целых чисел — координаты начальной (`x_s,y_s,z_s`) и конечной (`x_t,y_t,z_t`) точки путешествия. Далее следует `N` строк, содержащих 6 целых чисел — координаты концов "кротовых нор". Все координаты измеряются в парсеках и находятся в диапазоне от 0 до 10000, и нет точек с совпадающими координатами.

Вывести минимальное время путешествия в секундах с точностью не менее `10^{-6}`.

1
0 0 0 100 100 0
1 1 1 50 100 10

52.722246

Расстояние между двумя точками в пространстве вычисляется по формуле `root\ ((x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2)`

В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.

Шпиону необходимо открыть несколько кодовых замков для похищения секретной информации. Для открытия кодового замка используется панель из нескольких кнопок. На первом и третьем замке — три кнопки, на втором и четвёртом — четыре кнопки. Первоначально на замках все кнопки имеют красный цвет и замки закрыты. При нажатии на кнопку её цвет циклически меняется. На первом и втором кодовом замке цвет переключается с красный на зелёный и обратно, а на третьем и четвёртом замке цвет переключается с красного на жёлтый, затем на зелёный, затем снова на красный и т.д. Как только на панели будет установлена нужная цветовая комбинация, замок откроется.

У шпиона есть устройство, которое может быстро нажимать на кнопки, но для него нужна программа, обеспечивающая получение всех комбинаций. Программа определяется как последовательность номеров кнопок без пробелов, которые нужно нажать на замке. Например, замок с 2 кнопками с двумя цветовыми состояниями можно открыть программой "1121". После нажатия кнопки 1 на замке будет установлена комбинация "зелёный-красный", после повторного нажатия кнопки 1 на замке будет установлена комбинация "красный-красный" (которая не открывает замка), после нажатия кнопки 2 — комбинация "красный-зелёный", а после третьего нажатия кнопки 1 — комбинация "зелёный-зелёный". Все комбинации будут проверены этой программой. Можно придумать более короткую программу для открытия этого замка, например, "121" или "212".

Для каждого из 4 замков напишите программу для устройства, чтобы оно могло его открыть. Вы должны выслать текстовый файл, содержащий ровно 4 строки. В первой строке нужно написать программу для открытия замка с 3 кнопками и двумя цветовыми состояниями, во второй строке — для замка с 4 кнопками и двумя цветовыми состояниями, в третьей строке — для замка с 3 кнопками и тремя цветовыми состояниями, а в четвёртой строке — для замка с 4 кнопками и тремя цветовыми состояниями. Программы должны содержать только цифры 1,2,3,4, без пробелов. Если вы не можете написать программу для открытия какого-то из замком, поставьте в соответствующей строке символ - (минус).

Пример файла, который нужно выслать в качестве ответа.

123123
12341234
-
43214321

Даны программы (неправильные, но соответствующие требованиям) для 1,2 и 4 замка, для 3-го замка программа отсутствует.

Проверка, что программы для открытия замка проверяют все возможные комбинации. В этой подзадаче 4 теста, каждый тест оценивается в 15 баллов. Каждый тест проверяет программу для одного из 4 замков. Баллы за каждый тест начисляются независимо.

Проверка, что программы для открытия замка содержат минимальное количество команд (чтобы шпион смог открыть замки как можно быстрее). В этой подзадаче 4 теста, каждый тест оценивается в 10 баллов. Каждый тест проверяет программу для одного из 4 замков. Баллы за каждый тест начисляются независимо.

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

В зале ожидания на вокзале стоят `N` рядов из `M` кресел. Чтобы ожидающие не скучали, вместо некоторых кресел установлено `K` мощных Wi-Fi роутеров. Ожидающие стараются занять места ближе к роутерам, так как тогда они смогут смотреть ролики с Youtube или VK с более высоким разрешением, без задержек. Если пассажир сидит на месте с номером `c` в ряде `r`, а `i`-й роутер расположен на месте `C_i` в ряде `R_i`, то расстояние до `i`-го роутера вычисляется как `max(|r-R_i|,|c-C_i|)`, где `|x|` – абсолютное значение `x`. Креслам в зале ожидания был присвоен приоритет от 1 до `N*M-K`, меньшие номера получили кресла с меньшим расстоянием до ближайшего роутера, среди кресел с одинаковым расстоянием до роутеров более удобными считаются кресла, стоящие в ряду с меньшим номером, а среди них — с меньшим номером места в ряду. На рисунке показан приоритет кресел в зале ожидания с 4 рядами из 7 кресел, в котором установлены 2 роутера (их позиции помечены черным цветом). Темно-серым цветом выделены кресла, стоящие на расстоянии 1 от роутеров, светло-серым — на расстоянии 2, белым — 3.

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

Первая строка ввода содержит четыре целых чисел — количество рядов `N` (`2\ ≤\ N\ ≤\ 10^9`) и мест в ряду `M` (`2\ ≤\ M\ ≤\ 10^9`), количество роутеров `K` (`1\ ≤\ K\ ≤\ 100`, `K\ <\ N*M`), количество запросов `Q` (`1\ ≤\ Q\ ≤\ 100`). Далее следует `K` строк, содержащих два целых числа — местонахождение роутеров: номер ряда `R_i` (`1\ ≤\ R_i\ ≤\ N`) и номер места в ряду `C_i` (`1\ ≤\ С_i\ ≤\ M`). Среди них нет совпадающих. Далее следует строка, содержащая `Q` целых чисел в диапазоне от 1 до `N*M-K` – приоритеты кресел.

Вывести для каждого запроса на отдельной строке одно целое число — расстояние до ближайшего роутера от кресла с заданным приоритетом.

4 7 2 4
2 5
4 4
1 6 16 26

1
1
2
3

`2\ ≤\ N\ ≤\ 100`, `2\ ≤\ M\ ≤\ 100`, `1\ ≤\ K\ ≤\ 100`

В этой подзадаче 10 тестов, каждый тест оценивается в 4 балла. Баллы за каждый тест начисляются независимо.

`100\ <\ N\ ≤\ 1000`, `100\ <\ M\ ≤\ 1000`, `1\ ≤\ K\ ≤\ 100`

В этой подзадаче 10 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

`10^3\ <\ N\ ≤\ 10^9`, `10^3\ <\ M\ ≤\ 10^9`, `K=1`

В этой подзадаче 5 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

`10^3\ <\ N\ ≤\ 10^9`, `10^3\ <\ M\ ≤\ 10^9`, `1\ <\ K\ ≤\ 100`

В этой подзадаче 10 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.