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

Условие

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

Российский телефонный номер в международном формате выглядит следующим образом: +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

Задача B. Странный эллипс ≡

Условие

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

Оказалось, что представление инопланетян о расстоянии между двумя точками отличается от васиного: для них расстояние r между точками (x₁, y₁) и (x₂, y₂) считается по формуле r = |x₁ − x₂| + |y₁ − y₂|.

Инопланетяне также рассказали несколько интересных фактов о городе, в котором они живут на своей планете:

1. в городе имеется два главных здания, имеющих координаты (x₁, y₁) и (x₂, y₂) соответственно;
2. для каждой точки границы города сумма расстояний (вычисленных по инопланетной формуле) от неё до главных зданий постоянна и равна R.

Помогите Васе посчитать площадь инопланетного города, как это делают земляне.

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

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

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

Выходной файл должен содержать единственное вещественное число — площадь города.

Ограничения

Гарантируется, что площадь города положительна.

−10⁵ ≤ x₁, y₁, x₂, y₂, R ≤ 10⁵

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

0 0 0 0 7

24.5

1 1 2 2 3

3.5

Задача C. Слишком много способов ≡

Условие

Однажды школьник Вася пришел в недавно построенное новое здание университета на мастер-класс по информатике. Здание имеет форму куба, составленного из одинаковых аудиторий также кубической формы. Каждой аудитории присвоены три номера 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 ≤ 1000.

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

1 1 1 2 2 2

6

1 1 1 3 3 3

90

Задача D. Марфа Геннадьевна ест яйца ≡

Условие

У Марфы Геннадьевны есть любимая курица, которую она назвала Марфой. В определённые дни Марфа давала по яйцу, и Марфа Геннадьевна в тот же день съедала его. Марфа Геннадьевна записывала, в какие дни Марфа давала яйцо.

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

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

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

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

Далее следуют N целых чисел a_i — номера дней, в которые Марфа Геннадьевна съедала яйцо.

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

Требуется вывести в выходной файл слово GOOD, если Марфа Геннадьевна съедала не более двух яиц в неделю, и слово BAD, если найдётся хотя бы один промежуток из семи подряд идущих дней, в который она съедала более двух яиц.

Ограничения

1 ≤ N ≤ 100

1 ≤ a₁ < a₂ < … < a_N ≤ 1000

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

3
1 7 8

GOOD

5
1 7 9 12 17

BAD

Задача E. Баба Яга летит в гости ≡

Условие

В тридевятом царстве жила-была Баба Яга. А в тридесятом царстве жил-был Кощей Бессмертный. Однажды Баба Яга решила слетать в гости к Кощею в своей ступе.

Баба Яга будет лететь строго в плоскости, перпендикулярной земле. Пусть тридевятое царство, в котором живёт Баба Яга, находится в точке (x = a, y = 0), а тридесятое царство, в котором живёт Кощей Бессмертный, находится в точке (x = b, y = 0), a < b. Между этими царствами гористая местность. Профиль гор в плоскости полёта Бабы Яги задаётся ломаной с координатами вершин (x = x_i, y = y_i), i = 1, 2, ..., N, a = x₁ < x₂ < ... < x_N = b, y_i ≥ 0, y₁ = y_N = 0. Ступе будет сообщена некоторая начальная скорость, после чего она полетит в поле тяжести Земли по параболе (сопротивлением воздуха пренебрегаем). Баба Яга хочет попасть в точности в тридесятое царство, чтобы потом не пришлось идти пешком или запускать ступу ещё раз.

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

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

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

Входной файл содержит целое число N. Далее следуют N пар целых чисел x_i y_i.

Числа a и b определяются так: a = x₁, b = x_N.

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

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

Ограничения

3 ≤ N ≤ 1000

0 ≤ a = x₁ < x₂ < ... < x_N = b ≤ 1000

0 ≤ y_i ≤ 1000, y₁ = y_N = 0

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

3
1 0
2 1
3 0

1.0000

3
1 0
2 1
4 0

1.1250

4
2 0
3 9
4 5
6 0

12.0000

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

Условие

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

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

Марфа Геннадьевна бросает N игральных кубиков и подсчитывает сумму очков, выпавших на кубиках. Затем она умножает сумму очков на некоторый коэффициент — это и будет сумма пожертвования.

На каждом кубике с одинаковыми вероятностями выпадает одно из чисел от 1 до 6.

Марфу Геннадьевну интересует вероятностное распределение суммы очков на кубиках, то есть для каждого возможного значения суммы очков она хочет узнать вероятность того, что сумма очков примет такое значение.

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

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

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

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

Вероятности вывести с точностью до 10-ти знаков после запятой.

Ограничения

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

1

1 0.1666666667
2 0.1666666667
3 0.1666666667
4 0.1666666667
5 0.1666666667
6 0.1666666667

2

2 0.0277777778
3 0.0555555556
4 0.0833333333
5 0.1111111111
6 0.1388888889
7 0.1666666667
8 0.1388888889
9 0.1111111111
10 0.0833333333
11 0.0555555556
12 0.0277777778

Задача G. Рисунки инопланетян ≡

Условие

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

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

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

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

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

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

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

Ограничения

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

3

1

18

2

25

3

Задача H. Светофоры ≡

Условие

Студент Вася каждый день ездит на машине в университет учиться. Система дорог города, в котором живет Вася, представляет собой на карте прямоугольную сетку состоящую из N × M перекрестков. Дом, от которого отъезжает Вася, находится в левом верхнем углу карты, а университет — в правом нижнем углу.

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

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

Итак, Васе нужно успеть на первую пару! Но Вася — порядочный гражданин и не станет проезжать на красный свет. В то же время, скорость автомобиля и состояние дорог в городе позволяют ему перемещаться между светофорами настолько быстро, что временем перемещения можно пренебречь. (Т. е. время проезда между перекрёстками равно нулю).

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

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

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

Далее следует N × M расписаний светофоров, перечисленных в порядке обхода карты построчно. Первое число i−го расписания c_i — количество временных отрезков i−го светофора, за которым следует c_i пар целых чисел  — временные отрезки, когда i−ый светофор светит красным. Отрезки не пересекаются и отсортированы по возрастанию левой границы.

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

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

Ограничения

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

2 2
1 0 1
1 0 1
1 0 1
1 0 1

1

2 3
2 0 1 4 10
2 0 3 4 10
2 0 1 3 10
1 0 100
1 0 100   
1 0 100 

10

Задача I. Круглый налог ≡

Условие

В Неизвестной стране, территория которой имеет форму круга с центром в начале координат и радиусом r₀ км., берётся налог за проезд — G₀ рублей за километр. Правительство Неизвестной страны задумало провести налоговую реформу: выделить N Круглых районов и установить для них налог за проезд отдельно. i-ый Круглый район задаётся своим центром (x_i; y_i), радиусом r_i и величиной налога G_i. Если i−ый Круглый район целиком содержит в себе j-ый Круглый район, то на территории j-го Круглого района сохраняется налог G_j.

Президент Неизвестной страны, живущий в доме с координатами (x_s; y_s), решил устроить поездку по направлению (v_x; v_y) с целью инспекции и контроля. На банковской карте президента имеется M рублей. Помогите службе президента рассчитать в какую самую дальнюю точку (x_f; y_f) Неизвестной страны сможет попасть президент.

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

Входной файла содержит целые числа x_s y_s v_x v_y M r₀ G₀ N.

Далее следует N четвёрок целых чисел — x_i y_i r_i G_i.

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

Выходной файл должен содержать два вещественных числа — x_f y_f, с точностью не менее 2-х знаков после десятичной точки.

Ограничения

0 ≤ N ≤ 10⁴

−10⁴ ≤ x_s, y_s, v_x, v_y, x_i, y_i ≤ 10⁴

1 ≤ r_i ≤ 10⁴

0 ≤ G_i ≤ 10⁴

0 ≤ M ≤ 10⁹

Границы любой пары Круглых районов не имеют больше одной общей точки.

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

0 0  2 3  15
10 4
0

2.08 3.12

0 0  2 2  15
10 4
4
0 0  1  1
0 0  2  2
0 0  3  3
4 4  1  1

4.77 4.77