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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ M, W ≤ 1000

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

30 7

4 5

28 7

4

2 10

0 1

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

Условие

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

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

Даны координаты 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

Задача C. Средняя скорость ≡

Условие

Коля каждый день ездит из дома до кампуса ДВФУ на острове Русском. Он заинтересовался, с какой средней скоростью он едет? Средняя скорость — это отношение общего пройденного пути к общему времени.

Коля разбил весь путь следования на N равных по длине участков и измерил среднюю скорость на каждом из них. Даны числа v₁, …, v_N — средние скорости на каждом участке. Требуется найти среднюю скорость на всём пути следования.

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

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

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

Выходной файл должен содержать единственное вещественное число — среднюю скорость на всём пути следования. Число должно быть выведено с точностью не менее 4-х знаков после запятой.

Ограничения

1 ≤ N ≤ 100

1 ≤ v_i ≤ 100

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

2
40 60

48.0000

3
16 12 24

16.0000

4
40 10 20 30

19.2000

Задача D. С горы ≡

Условие

Однажды Андрей поднялся на гору Пидан. Когда он начал спускаться, то из-за усталости пошел не по той тропе и заблудился. Андрею известно, что все широкие тропинки, ведущие с вершины вниз, представляют собой дерево с N узлами, пронумерованными от 1 до N. Вершина горы соответствует корню дерева и имеет номер 1. Подножие горы, куда нужно попасть Андрею — самый удаленный от вершины лист дерева. Гарантируется, что такой лист ровно один.

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

Помогите Андрею найти кратчайший (использующий наименьшее количество тропинок) путь от листа x, где он находится сейчас, до подножия горы, проходящий не более чем по k узким тропинкам.

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

Входной файл содержит целые числа N P k x. Далее следуют N − 1 пара целых чисел u_i v_i, обозначающих, что узлы u_i и v_i соединены широкой тропинкой. Далее следуют P пар целых чисел w_j t_j, обозначающих, что узлы w_j и t_j соединены узкой тропинкой.

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

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

Ограничения

1 ≤ x ≤ N ≤ 10⁵, 0 ≤ k ≤ P ≤ 10,
1 ≤ u_i, v_i, w_j, t_j ≤ N, u_i ≠ v_i, w_j ≠ t_j.

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

11 2 2 8
1 2  1 3  2 4  2 5  3 6  3 7  5 8  7 9  7 10  10 11
5 6  6 7

5

11 2 1 8
1 2  1 3  2 4  2 5  3 6  3 7  5 8  7 9  7 10  10 11
5 6  6 7

6

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 31

1 ≤ a_i ≤ 20

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

2
8 5

1

3
5 8 7

4

Задача F. Сколько треугольников? ≡

Условие

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

Спрашивается: сколько всего треугольников на рисунке? (Учитываются треугольники разных размеров.)

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

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

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

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

Ограничения

1 ≤ N ≤ 1000

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

2

5

3

13

28

5985

Задача G. Кусочно-линейная функция ≡

Условие

Вася хочет построить алгоритм рисования графиков функций вида y = k₁|x + b₁| + k₂|x + b₂| + ...  + k_n|x + b_n|. Он понял, что это график кусочно-линейной функции, т.е. ось x можно разбить на интервалы ненулевой длины так, что на каждом из них график представляет из себя график линейной функции. А линейные функции алгоритм Васи рисовать уже умеет. Вася просит вас помочь ему определить, из каких линейных функций будет состоять его график.

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

Входной файл содержит целое число n, за которым следуют n пар целых чисел k_i b_i.

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

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

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

Ограничения

1 ≤ n ≤ 1000.

|k_i|, |b_i| ≤ 1000

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

1
1 1

2
-1 -1
1 1

2
1 2 3 2

2
-4 -8
4 8

2
2 2 -2 2

1
0 0

Задача H. IR-исполнитель ≡

Условие

IR-исполнитель работает с одним целым числом и может выполнять две команды:

• I — увеличить число на 1
• R — переставить цифры числа в обратном порядке, затем убрать лидирующие нули

Требуется определить последовательность команд IR-исполнителя, которая получит из числа x число y (x ≠ y).

Например, в результате применения последовательности команд IIRII к числу 8 будут получаться числа 9, 10, 1, 2, 3.

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

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

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

Выходной файл должен содержать единственную строку, состоящую из букв I и R — последовательность команд исполнителя. Если существует несколько последовательностей команд, выведите любую из них.

Ограничения

1 ≤ x, y ≤ 10⁹. Длина последовательности команд не должна превышать 200000 символов.

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

1 4

III

51 26

IRI

8 3

IIRII