Задача A. Радары ≡

Условие

В линейном царстве, в одномерном пространстве жили-были военные. Однажды у них возникла задача обнаружения объекта при помощи радаров, и они установили на прямой, где они живут, несколько радаров.

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

Даны координаты 2-х радаров и расстояния от этих радаров до объекта. Требуется определить, где находится объект.

Формат входного файла

Первая строка входного файла содержит целые числа a b — координаты точек, где находятся радары.

Вторая строка входного файла содержит целые числа d_a d_b — расстояния от объекта до радаров.

Формат выходного файла

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

Если радары выдали ошибочные показания и такой точки не существует, то нужно вывести в выходной файл два нуля.

Ограничения

−10⁹ ≤ a, b ≤ 10⁹

a ≠ b

1 ≤ d_a, d_b ≤ 10⁹

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

6 2
7 3

-1

-4 -1
1 1

0 0

0 100
50 50

50

Задача B. Межпланетные занятия ≡

Условие

Где-то в Млечном Пути есть межпланетное государство — Объединённая федерация планет. Совсем недавно в этом государстве был образован Межпланетный федеральный университет, расположенный на Луне, в Море Спокойствия, на острове Андорианском. Остров Андорианский соединён с материком мостом через лунный кратер.

В Межпланетном федеральном университете учатся и земляне, и один из них — Андроид, внук Марфы Геннадьевны. Ему очень нравится предмет "Квантовые вычисления". Занятия по этому предмету проводятся один раз в неделю (в один и тот же день недели). На Луне используется календарь, который не совпадает с земным, поэтому в месяце M дней, а в неделе W дней. Андроид заинтересовался, сколько раз в месяц могут проводиться занятия?

Напишите программу, принимающую на вход числа M и W и вычисляющую все возможные количества занятий в месяце.

Формат входного файла

Входной файл содержит целые числа M W.

Формат выходного файла

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

Ограничения

1 ≤ M, W ≤ 1000

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

30 7

4 5

28 7

4

2 10

0 1

Задача C. Мы делили... ≡

Условие

На день рождения пришли N гостей. Праздничный торт разделили между всеми гостями поровну. После этого неожиданно явились ещё K гостей.

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

Ответ вывести в виде несократимой обыкновенной дроби A / B.

Формат входного файла

Входной файл содержит два целых числа — N K.

Формат выходного файла

Выходной файл должен содержать два целых числа — A B, обозначающие числитель и знаменатель соответственно.

Ограничения

1 ≤ N, K ≤ 10⁴

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

1 3

3 4

3 9

1 4

Задача D. Слишком много простых способов ≡

Условие

Однажды школьник Вася пришел в недавно построенное новое здание университета на мастер-класс по информатике. Здание имеет форму куба, составленного из одинаковых аудиторий также кубической формы. Каждой аудитории присвоены три номера x, y, z — порядковые номера по ширине, длине и высоте соответственно. Самая первая аудитория имеет номера 1, 1, 1. Из каждой аудитории можно перейти в любую соседних, имеющих с ней общую стену.

Вася находится в аудитории (x_B, y_B, z_B). Мастер-класс пройдет в аудитории (x_M, y_M, z_M). Вася решил посчитать, сколькими способами можно попасть из текущей аудитории в ту, где проходит мастер-класс, за наименьшее число переходов между аудиториями.

Однако Вася частенько прогуливает мастер-классы и не знает как это сделать, поэтому он отправил смс-ку вам, в надежде, что вы подскажете ему ответ.

Формат входного файла

Входной файл содержит 6 целых чисел x_M y_M z_M x_B y_B z_B.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество способов. Так как ответ на вопрос Васи может быть слишком большим, выведите в его остаток от деления на 10⁹ + 7.

Ограничения

1 ≤ x_M, y_M, z_M, x_B, y_B, z_B ≤ 100.

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

1 1 1 2 2 2

6

1 1 1 3 3 3

90

Задача E. Правильная запись номера ≡

Условие

Руководство российского НИИ Абсолютно Симметричных Моделей (АСМ) решило внедрить систему электронного документооборота, включающую в себя контактные данные работников. Сотрудник отдела кадров столкнулся с проблемой: система позволяет вводить телефонные номера только в международном формате, а номера в анкетах работников записаны в произвольном формате, лишь позволяющим отделить код региона от локального номера. Более того, цифры, образующие локальный номер, могут быть разделены на группы с произвольным количеством цифр в каждой.

Российский телефонный номер в международном формате выглядит следующим образом: +7␣код_региона␣локальный_номер. В зависимости от длины кода региона существует 4 допустимых варианта записи:

• +7␣123␣123-45-67
• +7␣1234␣12-34-56
• +7␣12345␣1-23-45
• +7␣123456␣12-34

Сотрудник отдела кадров НИИ АСМ просит Вас написать программу, конвертирующую телефонный номер в международный формат.

Формат входного файла

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

Формат выходного файла

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

Ограничения

Каждый телефонный номер работника начинается с подстроки +7 после которой следует код региона и локальный номер. Код региона — первый блок подряд идущих цифр после +7. В качестве символов разделителя могут быть использованы пробелы (ASCII 32) и тире (ASCII 45). Код региона может быть также обрамлён круглыми скобками (ASСII 40 и ASСII 41), в этом случае символы разделителя вокруг скобок могут быть опущены.

Суммарное количество цифр в коде региона и локальном номере равно 10. Длина входной строки не превышает 25 символов.

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

+7 (123)456-7-890

+7 123 456-78-90

+7(9876)543 210

+7 9876 54-32-10

+7-31415 92 - 65-3

+7 31415 9-26-53

Задача F. Марфа Геннадьевна и часы - 2 ≡

Условие

Однажды Марфа Геннадьевна проснулась взволнованной. "Надо не забыть перевести часы на час назад", — подумала она. У Марфы Геннадьевны было двое часов. Одни механические, другие электронные. Электронные часы переводят время на час назад автоматически, механические — нет.

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

Марфа Геннадьевна обратилась к вам за помощью. Напишите программу, принимающую на вход записи Марфы Геннадьевны и вычисляющую все возможные моменты времени, когда электронные часы могли перевести время на час назад. Известно, что электронные часы перевели время ровно один раз на час назад в 1, 2, ..., 22 или 23 часа.

Формат входного файла

Входной файл содержит целое число N — количество записей Марфы Геннадьевны. Далее следуют N пар чисел a_i b_i, где a_i — количество часов, которое показывают механические часы, b_i — количество часов, которое показывают электронные часы.

Формат выходного файла

Требуется вывести в выходной файл целые числа, разделённые пробелами — все возможные моменты времени (часы), когда электронные часы могли перевести время, в порядке возрастания.

Ограничения

1 ≤ N ≤ 24

0 ≤ a_i ≤ 23; 0 ≤ b_i ≤ 22

a₁ < a₂ < … < a_N; b₁ ≤ b₂ ≤ … ≤ b_N

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

3
3 3
6 5
10 9

4 5 6

1
21 21

22 23

2
3 2
14 13

1 2 3

Задача G. Арифметическая прогрессия ≡

Условие

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

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

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

Формат входного файла

Входной файл содержит целое число N — количество чисел, за которым следуют N целых чисел a_i.

Формат выходного файла

Выходной файл должен содержать целое число M — количество чисел, которые останутся после вычёркивания (при этом количество вычеркнутых чисел должно быть минимальным).

Далее должны следовать M целых чисел — номера чисел, которые останутся после вычёркивания, перечисленные в порядке возрастания.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 10⁶

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

7
1 3 4 2 7 8 10

4
1 3 5 7

Задача H. Расписание электричек ≡

Условие

В одном городе есть железная дорога, на которой N станций расположены в ряд. Крайние станции называются Центр и Пригород. По этой железной дороге ходит одна электричка в обоих направлениях. Утром электричка начинает своё движение из Центра и идёт в Пригород со всеми остановками. Затем она идёт обратно в Центр, тоже со всеми остановками. Цикл "Центр — Пригород — Центр" электричка совершает K раз и вечером возвращается в Центр.

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

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

Формат входного файла

Входной файл содержит целые числа N K.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 100

1 ≤ K ≤ 25

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

4 1

3

5 2

2

Задача I. Минимальный лабиринт ≡

Условие

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

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

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

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

Формат входного файла

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

Далее идут N строк по M символов, описывающие лабиринт:

• # (ASCII 35) — обозначает блок
• . (ASCII 46) — обозначает пустое место

Формат выходного файла

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

Ограничения

1 ≤ N, M ≤ 100

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

3 7
......#
.#..#.#
....#..

......#
.#..#.#
....#..

3 8
##.#..##
##.#.###
...#.##.

.#.#..#.
##.#.#.#
...#.##.

Задача J. Гадание на ромашках ≡

Условие

Однажды Аполлинарий Матвеевич очутился на поле, на котором росли ромашки. Он сорвал несколько ромашек и стал гадать, любит или не любит его Марфа Геннадьевна. А гадал он так: брал каждую ромашку по отдельности и отрывал от неё лепестки, приговаривая: "любит", "не любит", "любит", "не любит"... Если при отрывании последнего лепестка он говорил "любит", то для этой ромашки ответ — "любит", а иначе для этой ромашки ответ — "не любит". Аполлинарий Матвеевич посчитал, сколько ромашек дали ответ "любит" и сколько ромашек дали ответ "не любит". Если количество ромашек с ответом "любит" строго больше, чем количество ромашек, давших ответ "не любит", то Аполлинарий Матвеевич считает, что Марфа Геннадьевна его любит. А в противном случае ромашки, увы, говорят обратное.

Аполлинарий Матвеевич задумался: сколько существует способов сорвать букет таким образом, чтобы ответ был "любит"?

Дано N — число ромашек на поле и числа a_i — количества лепестков на ромашках. Требуется определить, сколькими способами можно сорвать букет, чтобы ответ был "любит".

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a_i — количества лепестков на ромашках.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — число способов сорвать букет, чтобы ответ был "любит".

Ограничения

1 ≤ N ≤ 31

1 ≤ a_i ≤ 20

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

2
8 5

1

3
5 8 7

4