Задача A. Задача по математике ≡

Условие

Иван Петрович, учитель математики в средней школе города N-ска, хочет провести контрольную работу на тему «делимость целых чисел». Учитель хочет составить очень много различных вариантов контрольной работы, чтобы ученики не могли списать друг у друга.

Иван Петрович придумал следующую задачу: пусть даны целые числа A и N, найдите целое число B такое, что AB + A + B делится на N. Он решил составить несколько подобных задач, изменяя данные в условии задачи. Для того, чтобы быстро проверить решение задачи учениками учителю необходимо знать и ответы на эти задачи. Помогите Ивану Петровичу написать программу, которая будет решать его задачу для различных исходных данных, поможет сэкономить много времени и сил при подготовке и проверке контрольной работы.

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

Единственная строка входного файла содержит два целых числа A, N, разделённых знаком пробела – числа, которые будут использоваться для очередного варианта контрольной.

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

В выходной файл нужно вывести одно число B – ответ на задачу Ивана Петровича. Число B должно быть неотрицательным и не превышать 10⁹. Если такого B не найдется – необходимо вывести число −1.

Ограничения

1 ≤ A, N ≤ 10⁹

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

2 4

2

3 4

-1

Задача B. Почти беспрефиксные коды ≡

Условие

В теории кодирования часто используют беспрефиксные коды – наборы слов, ни одно из которых не является префиксом другого. Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова «», «a», «ab» и «aba» являются префиксами слова «aba». Например, набор слов «aba», «aa» и «bac» является беспрефиксным кодом, а набор «abac», «aba», «ba» – нет, поскольку слово «aba» является префиксом слова «abac».

Профессор главного университета города Соколовка де Фрошин дает задания нерадивым студентам по кодированию информации – почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор «abac», «abс», «ba» является почти беспрефиксным кодом уровня 2, а набор «abac», «abab», «ba» – уровня 3, поскольку наибольший общий префикс слов «abac» и «abab» имеет длину 3.

Задача, которую профессор де Фрошин поставил своим студентам, заключается в следующем: по заданному набору слов и числу k требуется выбрать из заданных слов максимальный набор, который является почти беспрефиксным кодом уровня k. А вас он просит написать программу для помощи в проверке ответов.

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

Первая строка входного файла содержит два целых числа: n и k – количество слов в заданном наборе и уровень почти беспрефиксного кода, который требуется построить. Следующие n строк содержат по одному слову. Слова состоят из строчных букв латинского алфавита. Длина каждого слова от 1 до 200 символов. Суммарная длина всех слов не превышает 10⁶. Все слова различны.

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

В первой строке выходного файла выведите одно число m – максимальное количество слов, которые можно выбрать из заданного набора, чтобы они образовывали почти беспрефиксный код уровня k. Следующие m строк должны содержать выбранные слова.

Ограничения

1 ≤ n ≤ 100 000

0 ≤ k ≤ 200

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

6 2
aba
bacaba
abacaba
baca
abac
caba

3
aba
bacaba
caba

Задача C. Мост ≡

Условие

Город Соколовка находится на берегах реки Флатовка, протекающей с юга на север. Жители города очень деловые и поэтому написали письмо мэру города с просьбой построить новый мост через реку для того, чтобы можно было перемещаться из одной части города в другую без автомобильных пробок. Однако возможности городского бюджета ограничены, поэтому мэр решил построить мост минимально возможной длины. Вдоль реки по обоим берегам проходят автомобильные дороги, поэтому выезд на мост можно сделать в любом месте.

Для упрощения задачи поиска местоположения моста, можно представить, что берега реки представляют собой ломаные, бесконечные в обе стороны. Введем координатную систему таким образом, чтобы ось OY была направлена с юга на север, а ось OX – с запада на восток. Левый берег начинается лучом, направленным на юг из точки (x_{1, 1}, y_{1, 1}), продолжается отрезками

(x_{1, 1}, y_{1, 1}) − (x_{1, 2}, y_{1, 2}), (x_{1, 2}, y_{1, 2}) − (x_{1, 3}, y_{1, 3}), …, (x_{1, m−1}, y_{1, m−1}) − (x_{1, m}, y_{1, m})

(x_{2, 1}, y_{2, 1}) − (x_{2, 2}, y_{2, 2}), (x_{2, 2}, y_{2, 2}) − (x_{2, 3}, y_{2, 3}), …, (x_{2, n−1}, y_{2, n−1}) − (x_{2, n}, y_{2, n})

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

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

Первая строка входного файла содержит целое число m. Следующие m строк содержат по два целых числа – координаты вершин ломаной левого берега: x_1,1; y_1,1, x_1,2; y_1,2, …, x_1,m; y_1,m.

Следующая строка входного файла содержит целое число n. Следующие n строк содержат по два целых числа – координаты вершин ломаной правого берега: x_2,1; y_2,1, x_2,2; y_2,2, …, x_2,n; y_2,n.

Известно, что x_1,1 < x_2,1, каждая из ломаных не имеет самопересечений и самокасаний, ломаные не имеют общих точек. Все отрезки каждой из ломаных имеют положительную длину. Все координаты не превосходят 10⁴ по абсолютной величине.

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

Выведите в выходной файл одно вещественное число: минимальную возможную длину моста. Ваш ответ будет проверяться с точностью 10⁻⁵.

Оптимальное положение моста показано на следующем рисунке:

Ограничения

2 ≤ m, n ≤ 100

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

4
6 1
3 1
3 0
0 3
3
9 3
2 3
6 5

1.41421356237309505

Задача D. Половинка ≡

Условие

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

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

Утром у Леши было n персиков, а за день он встретил k друзей. Выясните, сколько персиков у него могло остаться вечером.

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

Входной файл содержит два целых числа: n – количество персиков у Леши и k – количество встреченных им за день друзей.

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

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

Ограничения

(1 ≤ n, k ≤ 1000)

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

6 1

2
3.0 5.5

3 3

3
0.5 1.0 1.5