2017-2018 Командная олимпиада Казахстанского филиала МГУ (осенний тур)
A. Appetizing problem
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дважды в течение пары Азат пытался отпроситься, чтобы сбегать в столовую, но преподаватель был непреклонен. Кое-как дождавшись перемены, Азат понял, что рискует не успеть проделать весь свой путь: аудитория $$$\rightarrow$$$ лифт $$$\rightarrow$$$ столовая $$$\rightarrow$$$ лифт $$$\rightarrow$$$ новая аудитория. Расстояние от любой аудитории до лифта, как и расстояние от лифта до столовой, Азат пробегает за $$$T$$$ секунд; лифт ждать не надо — он всегда приезжает моментально; лифт движется со скоростью один этаж в секунду; ну и естественно, Азату нужно ровно $$$D$$$ секунд, чтобы покушать. Какой минимальной продолжительности должна быть перемена, чтобы Азат благополучно пообедал и не опоздал на следующую пару?

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

Четыре целых числа через пробел: $$$N_1$$$, $$$N_2$$$ (от 200 до 999), $$$T$$$ и $$$D$$$ (от 1 до 1000).

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

Одно целое число — время от выхода из аудитории $$$N_1$$$ до входа в аудиторию $$$N_2$$$ в секундах.

Примеры
Входные данные
714 601 25 300
Выходные данные
411
Входные данные
201 201 10 10
Выходные данные
52
Примечание

Аудитория с номером $$$N$$$ находится на этаже, номер которого является пер-вой цифрой числа $$$N$$$. Например, 714 аудитория находится на седьмом этаже. Столовая находится на первом этаже.

B. Bekarys' problem
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

А вот Бекарыс уже покушал и готов находить четвёртые справа цифры факториалов разных чисел. Ведь этим все и занимаются после плотного обеда, не так ли?

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

Одно целое число $$$N$$$ (от 1 до $$$10^{18}$$$).

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

Одно целое число от 0 до 9.

Примеры
Входные данные
3
Выходные данные
0
Входные данные
7
Выходные данные
5
Примечание

Если в десятичной записи числа $$$N!$$$ меньше четырёх цифр, вывести ноль.

C. Car showroom problem
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Да, дела у Надиры с её автосалоном идут хорошо. Правда, у него до сих пор нет названия. Надира даже частично выкупила авторские права на букву 'a'. Теперь она может использовать эту букву, но не слишком часто: ей нельзя ставить буквы 'a' рядом друг с другом. Сколько разных допустимых вариантов названий есть у Надиры?

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

Одно целое число $$$N$$$ от 1 до $$$10^7$$$ — количество букв в планируемом названии автосалона.

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

Количество допустимых вариантов — строк длины $$$N$$$ из строчных латинских букв, не содержащих двух букв 'a' подряд. Поскольку ответ может оказаться очень большим, его следует вывести по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
2
Выходные данные
675
Входные данные
2017
Выходные данные
379347254
Примечание

В первом примере допустимы все сочетания из двух букв, кроме «aa».

D. Dice problem
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Куб, находящийся во владении команды Снежный Куб и являющийся её талисманом, представляет собой кубик единичного размера. Одна его грань окрашена в красный цвет, противоположная ей — в синий, остальные четыре белы как снег. Кубик стоит на своей красной грани в левом верхнем углу доски $$$N \times M$$$. Тимур с Еруланом (только с разрешения Александры, конечно) могут перекатить куб через ребро на одну из четырёх соседних клеток доски, если она не занята. Какое наименьшее количество перекатываний им понадобится, чтобы этот куб оказался на своей начальной позиции, стоя на синей грани?

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

На первой строке два целых числа $$$N$$$ и $$$M$$$ от 1 до 100. В следующих $$$N$$$ строках матрица $$$N$$$ на $$$M$$$ — описание доски: '#' — недоступные клетки, '.' — свободные клетки. Гарантируется, что клетка, на которой изначально находится кубик, свободна.

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

Одно целое число — минимальное количество перекатов. Если такой последовательности перекатов не существует, вывести $$$-1$$$.

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

В первом примере подходит следующая последовательность: вниз, вправо, вправо, вниз, влево, влево, вверх, вверх.

E. Easy problem
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В нашем филиале чтят традиции. Вот и Куат, Димитрий и Павел переняли традицию команды Big Dipper пить чай на тренировках. Как и их старшие товарищи, они определили комфортную температуру чая, при которой его можно пить — от $$$L$$$ до $$$R$$$ градусов. Сейчас перед ними $$$N$$$ чашек с чаем. Сколько у них различных способов смешать чай из двух чашек так, чтобы получился чай комфортной температуры?

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

В первой строке три целых числа: $$$N$$$ — количество чашек, $$$L$$$ и $$$R$$$ — границы комфортной температуры чая, где $$$N$$$ от 2 до $$$10^5$$$, $$$-10^9 \leqslant L \leqslant R \leqslant 10^9$$$. Во второй строке $$$N$$$ целых чисел $$$x_i$$$ — температура чая в $$$i$$$-й чашке, где $$$x_i$$$ от $$$-10^9$$$ до $$$10^9$$$.

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

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

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

Смешивая две чашки чая с температурами $$$A$$$ и $$$B$$$, вы получите чай с температурой $$$\dfrac{A+B}{2}$$$. В первом примере смешать чай можно из любых двух чашек. Во втором примере условиям удовлетворяет только одна пара (1, 19).

F. Flat problem
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Плюс жизни под землёй в том, что вам не надо покупать жильё по высоким ценам, ведь вы можете вырыть себе квартиру сами! Как раз этим и занят домашний питомец Ануара — крот Кртек. Он начинает с одной свободной квадратной клетки. Затем он выбирает одно из четырёх направлений, расчищает, если нужно, соседнюю клетку в этом направлении и перемещается туда. Какое максимальное количество дверей сможет поставить крот Кртек так, чтобы из любой точки полученного жилища он мог попасть в любую другую, не пройдя ни через одну дверь?

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

Строка из не более, чем 1000 символов 'N', 'E', 'S', 'W', описывающая маршрут Кртека.

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

Ответ — максимальное количество дверей.

Примеры
Входные данные
NNNWSSSWNNN
Выходные данные
6
Входные данные
NNWWSSEE
Выходные данные
1
Примечание

Двери ставить можно только на границе двух смежных жилых клеток. Один из вариантов расстановки дверей в первом примере:

G. Golden problem
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Квадрат числа 26 равен 676 — палиндрому. Также палиндром получится, если в квадрат возвести 2285. Этими и подобными числами заинтересовался Рамазан, дав им название золотых. Все эти числа он мог бы выписать на полях Демидовича, но там слишком мало места. Каждому, кто сможет внести хоть какой-то вклад в развитие теории золотых чисел (то есть, не палиндромов, дающих палиндромы при возведении в квадрат), Рамазан обещает дать два пирожка: с картошкой и капустой. Не сто тысяч марок, конечно, но тоже достойная награда. Покажите, что вы заслуживаете этот приз.

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

В первой строке целое число $$$M$$$ от 1 до $$$10^5$$$ — количество запросов. В следующих $$$M$$$ строках по два целых числа $$$L_i$$$, $$$R_i$$$ такие, что $$$1 \leqslant L_i \leqslant R_i \leqslant 10^9$$$.

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

$$$M$$$ строк, на каждой из которых одно целое число — количество золотых чисел в сегменте $$$[L_i, R_i]$$$.

Пример
Входные данные
3
2 3
22 33
222 333
Выходные данные
0
1
2
Примечание

Золотыми числами из третьего запроса являются 264 и 307 ($$$264^2=69696$$$, $$$307^2=94249$$$).

H. Honey cake problem
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

«С понедельника никакого сладкого!» — твёрдо решил Илья. Но пока только суббота и перед ним на столе медовый торт. На коробке написано «Звёздный торт», но Илья относится к этому названию с некоторой долей скепсиса. Всем ведь известно, что $$$2n$$$-угольный торт может называться звёздным, только если углы, от которых можно отрезать треугольный кусок, чередуются с углами, от которых нельзя отрезать треугольный кусок. Помогите Илье определить, является ли данный торт звёздным на самом деле.

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

Одно целое число $$$M$$$ от 3 до 1000 — количество вершин торта. Далее $$$M$$$ пар целых чисел от $$$-1000$$$ до $$$1000$$$ — координаты вершин. Вершины перечислены в порядке обхода против часовой стрелки.

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

Если этот торт является звёздным, вывести «YES» (без кавычек), иначе «NO» (также без кавычек).

Примеры
Входные данные
8
10 0
1 1
0 10
-1 1
-10 0
-1 -1
0 -10
1 -1
Выходные данные
YES
Входные данные
4
10 0
1 1
0 10
-10 -10
Выходные данные
NO
Примечание

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

I. Is that even a problem?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Абырвалг. Поехали!

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

Три целых числа А, В, С от $$$-1000$$$ до 1000.

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

Одно целое число.

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