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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ M, W ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
30 7
4 5
2
28 7
4
3
2 10
0 1

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

 − 109 ≤ a, b ≤ 109

a ≠ b

1 ≤ da, db ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 2
7 3
-1
2
-4 -1
1 1
0 0
3
0 100
50 50
50

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ vi ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
40 60
48.0000
2
3
16 12 24
16.0000
3
4
40 10 20 30
19.2000

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

Автор:О. Ларькина   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ x ≤ N ≤ 105, 0 ≤ k ≤ P ≤ 10,
1 ≤ ui, vi, wj, tj ≤ N, ui ≠ vi, wj ≠ tj.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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
2
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. Гадание на ромашках

Автор:Г. Гренкин, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 31

1 ≤ ai ≤ 20

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
8 5
1
2
3
5 8 7
4

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
5
2
3
13
3
28
5985

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

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Вася хочет построить алгоритм рисования графиков функций вида y = k1|x + b1| + k2|x + b2| + ...  + kn|x + bn|. Он понял, что это график кусочно-линейной функции, т.е. ось x можно разбить на интервалы ненулевой длины так, что на каждом из них график представляет из себя график линейной функции. А линейные функции алгоритм Васи рисовать уже умеет. Вася просит вас помочь ему определить, из каких линейных функций будет состоять его график.

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

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

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

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

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

Ограничения

1 ≤ n ≤ 1000.

|ki|, |bi| ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1 1
2
-1 -1
1 1
2
2
1 2 3 2
2
-4 -8
4 8
3
2
2 2 -2 2
1
0 0

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

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 4
III
2
51 26
IRI
3
8 3
IIRII

0.667s 0.008s 31