Задача A. Эксперимент ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

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

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

За экспериментом наблюдал лучший друг Раджеша, Говард Воловиц. По результатам встречи Раджеша с i-той девушкой, в блокноте Говарда появлялось число a_i. Модуль числа был равен количеству сказанных во время разговора слов, оно было положительным, если говорил Раджеш, и отрицательным, если девушка. Если же Раджеш и девушка игнорировали друг друга, в блокноте появлялся ноль.

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

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

В первой строке входного файла содержатся два целых числа: N (1 ≤ N ≤ 1000) — количество девушек, встретившихся Раджешу, и D(|D| ≤ 1000) — среднее арифметическое чисел, записанных Говардом.

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

В первую строку выходного файла выведите ровно N различных целых чисел a_i(|a_i| ≤ 10000), разделенных пробелами. Среднее арифметическое всех выведенных Вами чисел должно быть равно ровно D.

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

2 3

2 4 

4 -5

-6 -4 -7 -3 

Задача B. Округление ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

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

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

Например, число 4.6445 будет округляться так: 4.6445 ↦ 4.645 ↦ 4.65 ↦ 4.7.

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

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

В первой строке задано целое число m (1 ≤ m ≤ 1000) — количество цифр после запятой в числах, количество которых интересует Говарда. Во второй строке задано вещественное число k (0 < k ≤ 1000) — полученное в результате округления число. Количество цифр после запятой в числе k — натуральное число, меньшее m.

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

Выведите единственное число — искомое количество способов.

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

2
1.1

10

Задача C. Туча над городом ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

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

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

У Леонарда есть только один шанс склонить власти на свою сторону — провести испытания тучи, наблюдая за уменьшенной версией и новейшим макетом города в течение T секунд. Макет города имеет форму огромного прямоугольника, на котором отмечены все улицы города. Все улицы считаются бесконечными полосками, параллельными либо левому, либо нижнему краю макета. Испытания будут проводиться следующим образом: тучку разместят над макетом так, что ее стороны будут параллельны его сторонам, а левый нижний угол совпадет с левым нижним углом макета. Затем смоделируют ветер: в течение секунды туча не будет двигаться, затем моментально переместится на заданный вектор, и так все T секунд. До начала испытания макет хранится в строжайшей тайне и может выглядеть практически как угодно. Например, так:

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

Решения, работающие при M = 0, U = 0, V = 0, будут оцениваться из 20 баллов.

Решения, работающие при M = 0, будут оцениваться из 40 баллов.

Решения, работающие при x_i + w_i, y_i + h_i ≤ 1000, T ≤ 100, будут оцениваться из 60 баллов.

Рисунок в условии соответствует первому примеру.

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

В первой строке находятся четыре целых числа: N — количество улиц в городе, параллельных левому краю макета, M — количество улиц в городе, параллельных нижнему краю макета, T — время наблюдения за тучей, S — количество снега, выпадающее на один квадратный метр за секунду (0 ≤ N, M ≤ 10⁴, 0 < N + M, 1≤ T ≤ 10⁶, 1 ≤ S ≤ 100).

В следующей строке находятся четыре целых числа: H, W — длины сторон тучи, параллельные левому и нижнему краю макета (1 ≤ H, W ≤ 10⁵); U, V — на сколько увеличивается расстояние от тучи до левого и нижнего краев макета, соответственно, при ее сдвиге (0 ≤ U, V ≤ 10⁵).

В следующих N строках содержится по два целых числа x_i, w_i — расстояние от левого края макета до левой стороны улицы и ее ширина (0 ≤ x_i ≤ 10⁵, 1 ≤ w_i ≤ 10⁵).

В следующих M строках содержится по два целых числа y_i, w_i — расстояние от нижнего края макета до нижней стороны улицы и ее ширина (0 ≤ y_i ≤ 10⁵, 1 ≤ w_i ≤ 10⁵). Никакие две параллельные улицы не пересекаются и не имеют общих сторон.

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

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

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

1 1 10 1
3 2 1 1
5 1
5 2

14

2 0 10 1
2 2 1 0
1 1
3 2

12

Задача D. Травля тараканов ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Произошло ужасное — в квартире доктора Шелдона Купера завелись тараканы! Пока все насекомые не будут убиты, Шелдон не успокоится.

Чтобы вычислить тараканьи гнезда, Шелдон поймал одного таракана. Проведя эксперимент, доктор выяснил, что этот таракан является разведчиком, а значит посещает все гнезда. Установив на таракане маленький передатчик, Шелдон отпустил его.

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

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

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

Сможете ли Вы написать такую программу?

Решения, работающие для n ≤ 18, будут оцениваться из 40 баллов.

Решения, работающие для n ≤ 10 000, будут оцениваться из 70 баллов.

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

В первой строке входного файла содержатся целые числа n и k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 100) — количество гнезд и наибольшее разрешенное расстояние от гнезда до ближайшего зараженного.

Следующие n−1 строк содержат описание ребер дерева. Каждая строка содержит описание одного ребра — номера гнезд, которые соединяет это ребро. Гнезда нумеруются целыми числами от 1 до n.

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

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

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

1 1

1

3 1
1 2
2 3

1

3 0
1 2
2 3

3