Задача 1. В ожидании Нового года ≡

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

Поэтому им хотелось бы иметь компьютерную программу, принимающую на вход текущее время (часы и минуты) и вычисляющую, сколько времени осталось до Нового года.

Число секунд в текущем времени принять равным 0.

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

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

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

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

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

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

12 0

12 0

23 59

0 1

22 25

1 35

Задача 2. Куб со спицами ≡

Условие

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

Требуется сложить куб так, чтобы любая спица проходила сквозь кубики всех N цветов.

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

Во входном файле содержится единственное натуральное число N.

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

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

Ограничения

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

2

1 2
2 1
2 1
1 2

Задача 3. Отгадай слово ≡

Условие

Хрюша и Степашка играют в игру "Отгадай слово". Правила игры просты. Хрюша придумывает слово, состоящее из букв латинского алфавита, придумывает загадку и загадывает её Степашке. Задача Степашки — отгадать слово.

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

Ход Степашки заключается в том, что Степашка называет любую букву латинского алфавита.

1. Если такая буква есть в слове и все такие буквы закрыты, то все они открываются.
2. Если такая буква есть в слове и все такие буквы открыты, то все они закрываются.
3. Если такой буквы нет в слове, то никакие буквы не открываются и не закрываются.

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

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

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

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

Вторая строка входного файла также состоит из маленьких букв латинского алфавита и представляет собой последовательность букв, которые называет Степашка (буквы идут в том порядке, в котором их называет Степашка).

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

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

Если i-я буква открыта, то i-й символ выходной строки должен совпадать с i-м символом первой строки входного файла.

Если же буква закрыта, то соответствующий символ выходной строки должен быть '.' (точка).

Ограничения

Количество букв в слове от 1 до 15.

Количество ходов Степашки от 1 до 20.

Входные данные таковы, что если в ходе игры Степашка отгадал все буквы слова, то игра заканчивается и Степашка больше не называет буквы (входной файл на этом заканчивается).

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

frog
or

.ro.

frog
oro

.r..

frog
fffrrroooog

fr.g

frog
golf

f.og

frog
gorf

frog

Задача 4. Кепка ≡

Условие

Если положить α  = 0, то поверхность K будет описываться формулами в последней строке, где нужно принять z равным 0.

Вот пример кепки при R = 10, L = 20.

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

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

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

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

Ограничения

1 ≤ R ≤ L ≤ 100

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

10 20

785.39816340

10 10

628.31853072

Задача 5. В пределе ≡

Условие

Здесь вы можете нарисовать звездочку.

Пусть числа R, r фиксированы. Площадь фигуры, ограниченной звездой с n лучами, обозначим через S_n. Положим S = limn ↦ ∞S_n.

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

Входной файл содержит вещественные числа R r.

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

Выходной файл должен содержать число S с точностью не менее 3 знаков после десятичной точки.

Ограничения

0 < r ≤ R ≤ 100

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

1 0.4

1.25664

Задача 6. Двоичные последовательности ≡

Условие

Здравствуй, юный падаван!

Прошу тебя вывести все двоичные последовательности длины N.

Реши задачу двумя способами:

• рекурсивным перебором
• прибавлением 1 к числу в двоичной системе счисления

Да пребудет с тобой произведение массы на ускорение!

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

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

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

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

Ограничения

1 ≤ N ≤ 15

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

2

00
01
10
11

Задача 7. Принтер - 2 ≡

Условие

Аполлинарий Матвеевич недавно купил новый принтер и решил распечатать на нём одну главу из своей любимой книги по микроэлектронике.

Входной и выходной лотки принтера горизонтальные. Принтер работает так: стопка бумаги загружается во входной лоток, принтер берёт по очереди листы от верхнего до нижнего и печатает на них страницы от последней до первой. Принтер печатает на той стороне листа, которая находится сверху во входном лотке, и в выходном лотке эта сторона листа тоже будет сверху. Таким образом, если положить в лоток 3 чистых листа бумаги и распечатать страницы с 1-й по 3-ю, то в выходном лотке страницы будут в таком порядке: 1, 2, 3.

Чтобы использовать меньше бумаги и чтобы распечатки было легче переплести, Аполлинарий Матвеевич предпочитает двустороннюю печать. Такой способ печати обычно вызывает у Аполлинария Матвеевича головную боль, если рядом нет внука-программиста, — текст распечатывается не так, как нужно.

Возможные дефекты:

1. При перелистывании распечатки может оказаться, что страницы расположены в неправильном порядке: 2, 1, 4, 3, ... вместо 1, 2, 3, 4, из-за чего приходится переворачивать каждый лист.
2. Первый лист может оказаться пустым с одной стороны, и Аполлинарий Матвеевич хочет, чтобы пустота была только на последнем листе.

Напишите программу, принимающую на вход диапазон страниц a… b и выводящую минимальную по длине последовательность инструкций для Аполлинария Матвеевича. В начальный момент времени во входном лотке лежит достаточно много чистых листов бумаги.

Коды инструкций:

• 1 — распечатать только нечётные страницы;
• 2 — распечатать только чётные страницы;
• 0 — положить чистый лист сверху стопки, лежащей на столе;
•  − 1 — достать стопку из выходного лотка и положить на стол;
•  − 2 — положить стопку со стола во входной лоток;
• 3 — перевернуть стопку, лежащую на столе.
• 100 — стопка бумаги лежит на столе, и при перелистывании будут просмотрены страницы a,a + 1,…,b. Пойти выпить чаю и съесть французских булок.

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

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

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

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

Ограничения

1 ≤ a ≤ b ≤ 1000.

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

1 1

1 -1 100

1 10

2 -1 3 -2 1 -1 100

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

Условие

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

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

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

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

Входной файл содержит целое число 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

Задача B. Многократное суммирование ≡

Условие

Дан массив целых чисел a₁, a₂, ..., a_N и дано M команд типа "найти сумму чисел a_i для i от l до r".

Требуется написать программу, выполняющую данные команды.

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

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

Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел l_j r_j.

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

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

1 ≤ l_j ≤ r_j ≤ N

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

5
1 2 3 4 5
3
1 3
2 5
3 5

6 14 12

Задача C. Количество каждого числа ≡

Условие

Вася записал в файл input.txt N чисел. Когда Петя открыл этот файл, он решил посчитать, сколько раз в файле записано каждое число.

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

Заметим, что это позволяет выполнить сортировку массива чисел по возрастанию при помощи простого подсчёта.

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

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

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

Выходной файл должен содержать пары чисел: число из входного файла и количество раз, сколько оно встретилось в файле.

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

Ограничения

1 ≤ N ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

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

4
1 2 1 0

0 1
1 2
2 1

7
9 1 3 2 3 -2 7

-2 1
1 1
2 1
3 2
7 1
9 1

Задача D. Деревья ≡

Условие

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

Даны значения высот N деревьев аллеи. Требуется найти два дерева, сумма высот которых максимальна и при этом расстояние между ними не меньше d. Расстояние — это разница порядковых номеров деревьев.

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

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

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

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

Ограничения

2 ≤ N ≤ 100000.

1 ≤ d ≤ N − 1.

1 ≤ a_i ≤ 10⁹.

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

7 4
3 4 5 6 7 1 2

10

5 3
1 2 3 4 1

5

Задача E. Марфа Геннадьевна и документы ≡

Условие

У Марфы Геннадьевны есть папка с файлами (не компьютерная, а обычная), в которую она складывает свои документы. Марфа Геннадьевна пронумеровала свои документы от 1 до N и уже привыкла к тому, что у неё в первом файле лежит первый документ, во втором файле — второй и т.д.

Однажды к Марфе Геннадьевне пришёл в гости внук и стал рассматривать её документы. Разумеется, после этого документы оказались не на своих местах.

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁵, 1 ≤ a_i ≤ N. Все числа a_i различны.

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

3
1 3 2

4
-3 2
-2 3
3 3
2 2

4
1 4 2 3

6
-4 2
-3 4
4 4
-2 3
3 3
2 2

3
1 2 3

0

Задача F. Арифметическая прогрессия ≡

Условие

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

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

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

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

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

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

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

Далее должны следовать M целых чисел — номера чисел, которые останутся после вычёркивания, перечисленные в порядке возрастания.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 10⁶

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

7
1 3 4 2 7 8 10

4
1 3 5 7

Задача G. Перевод длинных чисел ≡

Условие

Дано неотрицательное целое число a, записанное в системе счисления по основанию p. Требуется перевести это число в систему счисления по основанию q. Для представления цифр больше 9 используются заглавные латинские буквы (A — 10, B — 11, &hellip;, Z — 35).

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

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

Ограничения

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

2 10
10010

18

31 17
AF2J5

6DG3BE

Задача H. НОД и числа Фибоначчи (исправленная) ≡

Условие

k-тым числом Фибоначчи называется k-тый член последовательности F_k = F_k − 1 + F_k − 2 , F₀ = 0 , F₁ = 1

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

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

В выходном файле должно содержаться единственное число — наибольший общий делитель F_n и F_k.

Ограничения

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

1 2

1

6 9

2

Problem I. Digitalization ≡

Statement

Define the function rm sum_of_digits(a) 〈 a ∈ N₀〉   = k∑i = 0a_i where {a_i} is the representation of a in the numeral system with radix 10.

Define the function:

rm digitalization(a) 〈 a ∈ N₀〉   = {
  bf if  rm sum_of_digits(a) ∈ 0..9  {
   bf return  rm sum_of_digits(a)
  }
  bf else  {
   bf return  rm digitalization(rm sum_of_digits(a))
  }
}

Your problem is to find rm digitalization(n!) for given n.

Input file format

n

Output file format

rm digitalization(n!)

Constraints

Sample tests

2

2

3

6

Задача J. Митинг ≡

Условие

Виртуальный студсовет принял решение провести митинг против свободы слова. В связи с этим встал вопрос о выборе председателя. В студсовете полно народу, и не из кого выбрать. Посовещавшись, виртуальные персонажи занумеровали себя и для персонажа с номером i определили следующие числа:

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

Напишите программу, составляющую список кандидатов на роль председателя.

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

Входной файл содержит натуральное число n  — количество персонажей. Далее следует n троек натуральных чисел m_i p_i t_i.

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

Требуется вывести в выходной файл номера отобранных персонажей в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

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

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

Задача K. Две пешки и слон ≡

Условие

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

Шахматная доска имеет размер 8 на 8. Слон бьет ближайшую фигуру на каждом из четырех диагональных направлений от себя.

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

Входной файл содержит числа x₁ y₁ x₂ y₂ — координаты первой и второй пешек.

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

Если задача имеет решение, то выходной файл должен содержать два числа — координаты слона. Если решений несколько, вывести любое из них. Если задача не имеет решения, вывести единственное число 0.

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

3 6 7 5

0

3 4 5 6

4 5

4 5 5 6

0

Задача L. WK ≡

Условие

В рамках социального проекта ЦПД в кампусе ДВФУ была организована социальная сеть WK, чтобы студенты могли обмениваться через неё учебными материалами и решать все насущные вопросы.

У каждого пользователя этой сети есть список контактов. Однажды в сеть WK поступил вброс о том, что студентам стали снижать оценки за лайки не(у)годным преподавателям.

Однажды утром на департамент мемов матфака поступило видео из серии "Капоэйра в неожиданных местах", в котором сотрудник кафедры информатики, математического и компьютерного моделирования ШЕН рассказал о произошедшем языком танца. Затем из этого видео выбрали понравившийся фрагмент и стали распространять в сети WK как мем.

Итак, однажды утром админ группы "Учеба каждый день, какой ужас" переслал всем своим контактам этот мем. Вечером его контакты получили мем.

Затем информация распространялась по сети WK следующим образом.

1. Сообщения отправляются только утром, а получаются только вечером.
2. Если пользователь B получил информацию от пользователя A, то утром следующего дня пользователь B разошлёт эту информацию всем своим контактам, от которых он не получал эту информацию и которым он не отправлял эту информацию.

Социальная сеть WK устроена таким образом, что если пользователь B находится в списке контактов пользователя A, то и пользователь A находится в списке контактов пользователя B. Никакой пользователь не может находиться в своём же списке контактов.

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

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

Первая строка входного файла содержит целое число N — количество пользователей социальной сети WK.

Далее для каждого пользователя во входном файле записана следующая информация. Сначала идёт целое число k_i — количество пользователей в списке контактов пользователя i, за которым следуют k_i различных целых чисел от 1 до N — номера пользователей из списка контактов i-го пользователя.

Админ группы "Учеба каждый день, какой ужас", он же админ группы "Стримы от Малявина" — это пользователь с номером 1.

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

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

Ограничения

1 ≤ N ≤ 100.

0 ≤ k_i < N.

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

3
2  2 3
1  1
1  1

0 1 1

3
2  2 3
2  3 1
2  1 2

0 2 2

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

0 1 1 1 2 0

Задача M. Лабиринт ≡

Условие

Лабиринт задан как двумерный массив символов '.' и '#', означающих пустое пространство и стену соответственно. В любой не занятой стеной клетке может находиться Искатель. Ему разрешено перемещаться по клеткам лабиринта в четырех направлениях: вверх, вниз, влево и вправо. Покидать лабиринт через внешнюю границу запрещено, ибо за его пределами находится сплошная стена. Требуется написать программу, которая по заданному лабиринту определяет существует ли путь от входа к выходу.

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

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

Ограничения

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

3 3
S#.
.#F
...

YES

3 3
S#.
.#F
#..

NO

Задача N. Лабиринт ≡

Условие

Лабиринт размером N x N клеток задан массивом символов. Символ '#' обозначеет стену, символ '.' — проход. Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.

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

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

Первая строка входного файла содержит размер лабиринта N.

Следующие N строк содержат по N символов — описание лабиринта.

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

Выходной файл должен содержать единственное целое число — длину кратчайшего пути, либо &minus;1, если пути не существует

Ограничения

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

2
.#
..

2

2
.#
#.

-1

Задача O. Марфа Геннадьевна и angry birds ≡

Условие

Недавно Марфа Геннадьевна увидела у внука на компьютере игру Angry birds и тоже захотела сыграть в такую игру. Она взяла кур, свиней и решила стрелять курами в свиней из рогатки. Марфа Геннадьевна задумалась: может, не стоит мучить бедных животных и сделать то же самое не с животными, а с математической моделью?

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

Тело имеет массу m кг, начальная скорость равна v₀ м/с и направлена под углом α градусов к горизонту. Ускорение свободного падения принять равным g = 9.8 м/с². Сила сопротивления воздуха равна .

Требуется определить время и дальность полёта курицы.

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

Входной файл содержит вещественные числа m v₀α k.

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

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

Ограничения

0.1 ≤ m ≤ 10

0.1 ≤ v₀ ≤ 20

1 ≤ α  ≤ 90

0 ≤ k ≤ 10

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

1 10 45 0

1.443 10.204

1 10 45 1

1.206 4.955

Задача P. Косточки для собак ≡

Условие

Однажды стая из N собак нашла M косточек. Теперь собаки хотят поделить косточки между собой. В стае действует безоговорочное правило: если одна собака старше другой, то она должна получить не меньше косточек, чем младшая.

Сколько существует способов распределить косточки между собаками, чтобы каждая собака получила хотя бы одну кость?

Например, если собак 2, а косточек 4, то существует 2 способа: либо младшей 1 кость, а старшей 3, либо младшей и старшей по 2 кости.

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

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

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

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

Ограничения

1 ≤ N ≤ M ≤ 50.

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

2 4

2

3 6

3

Задача Q. Барабанная почта ≡

Условие

Когда-то давно члены одного африканского племени, жившие в разных деревнях, использовали для передачи информации звуковую почту. Чтобы передать сообщение, отправитель бил в барабан в промежутки времени a_i ≤ t ≤ b_i, а получатель слушал и рассказывал жителям своей деревни. Сила звука зависит от погоды — например, во время дождя и грозы звук барабана практически не слышен.

Однажды у племени поменялся вождь, и необходимо было оповестить об этом всех жителей племени. Но, как назло, погода в этот день была очень неустойчивая — то дождь, то туман, то ветер, то солнце. Поэтому звуки барабана можно было слышать только в промежутки времени c_i ≤ t ≤ d_i.

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

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

Входной файл содержит целое число N — количество промежутков [a_i, b_i]. Далее следуют N пар целых чисел a_i b_i. Далее во входном файле содержится целое число M — количество промежутков [c_i, d_i], — за которым следуют M пар целых чисел c_i d_i.

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

Выходной файл должен содержать целое число K — количество промежутков [e_i, f_i] — и K пар целых чисел e_i f_i.

Должны выполняться неравенства: f_i < e_i + 1, i = 1, …, K − 1.

Промежутки нулевой длины выводить не нужно.

Ограничения

1 ≤ N, M ≤ 1000, 0 ≤ a_i < b_i ≤ 10000, 0 ≤ c_i < d_i ≤ 10000

b_i < a_i + 1, i = 1, …, N − 1

d_i < c_i + 1, i = 1, …, M − 1

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

3
0 3
5 9
12 14
3
1 4
5 11
13 15

3
1 3
5 9
13 14

2
0 4
7 10
2
5 7
10 13

0

Задача R. Сколько лепестков? ≡

Условие

Здесь можно узнать, любит ли тебя он/она. Введи ваши дни рождения, скрипт нарисует цветок, и тебе только останется сосчитать лепестки.

Примечание. Вопросы по всем задачам турнира вы можете задавать здесь.

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

Входной файл содержит 4 целых числа: день и месяц (М) и день и месяц (Ж).

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

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

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

1 1  15 5

7

Задача S. Числовые ребусы ≡

Условие

Однажды юному программисту Серёже попалась книга с головоломками. Ему особенно понравилось решать числовые ребусы. Он решил большое количество ребусов, но иногда у него получались ответы, не совпадающие с ответами в книге. Поэтому Серёже очень пригодилась бы программа, вычисляющая все возможные ответы к данному числовому ребусу.

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

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

Во 2-м примере должно быть написано 2014 + ГОД = СОЧИ, но из-за того, что русские буквы в примерах не отображаются, они были заменены на другие буквы.

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

Входной файл содержит 3 строки, представляющие собой числа, в которых некоторые цифры заменены на не цифровые символы с ASCII-кодом больше 32.

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

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

Выводить следует те ответы, в которых нет незначащих нулей в начале чисел.

Ограничения

Количество символов в каждом числе во входном файле не превосходит 9.

Общее количество не цифровых символов во всех числах находится в пределах от 1 до 6.

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

drama
drama
teatr

18969
18969
37938

2014
AOB
CODE

2014
789
2803

2014
891
2905

2014
893
2907

2014
896
2910

OXOXO
AXAXA
AXAXAX

90909
10101
101010

2A14
AAB
AODE

2214
221
2435

2214
225
2439

Задача T. Робот, налево! ≡

Условие

В Центре робототехники изобрели робота, который ходит только налево. На вопрос "зачем?" он затрудняется ответить.

Робот занимает одну клеточку и действует по следующему алгоритму.

1. Развернуться влево.
2. Если следующая клеточка не была посещена ранее, то пойти прямо (1). Иначе развернуться вправо и пойти прямо (2).

За шаг вида (1) робот получает 1 очко, за шаг вида (2) — 0 очков. Сколько очков получит робот, сделав N шагов?

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁹

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

1

1

3

3

15

7

Задача U. Новогодний код ≡

Условие

Деду Морозу из Нью-Васюков пишут не стихи, а проги. Дед Мороз любит, когда код программы похож на его бороду, то есть длины строк кода {a_i}Ni = 1 удовлетворяют условию

a₁ < a₂ > a₃ < a₄ > …    ∧   a₁ > a₂ < a₃ > a₄ < ….

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

Напишите программу, которая по указанным длинам строк кода a_i определяет новый набор длин b_i, в котором:

1. a_i ≤ b_i,
2. либо b₁ < b₂ > b₃ < b₄ > …, либо b₁ > b₂ < b₃ > b₄ < …
3. сумма b_i минимальна.

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

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

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

Входной файл должен содержать N целых чисел b_i — новые длины строк. Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 100; 1 ≤ a_i ≤ 100

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

1
20

20

4
11 10 11 15

11 12 11 15

Задача V. Бутылка на всех ≡

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

Задача W. Посейдон ≡

Условие

На этапе автоматизации технического обслуживания прачечной создатели сервиса управления расписанием стирки "Посейдон" (poseidon.dvfu.ru) столкнулись с алгоритмической проблемой.

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

Сервис "Посейдон+" (для персонала) должен вывести алгоритм перемещения поломанной машинки в заданное место с координатами (N, M), на котором машинка не стоит.

Задача разработчиков системы "Посейдон+" — реализовать алгоритм, который найдет оптимальный способ такого перемещения. "Оптимальный" — значит за минимальное число элементарных операций. Элементарная операция — это перемещение любой стиральной машины на свободное место, соседнее с ней по горизонтали или вертикали.

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

N, M ∈ N.

Способ представления стандартный.

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

x ∈ N₀ — решение задачи оптимизации — минимальное количество перемещений (указания персоналу выводить не нужно).

Способ представления стандартный.

Ограничения

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

2 2

5

5 3

23

3 7

35

Задача X. Годы летят ≡

Условие

В пожилом возрасте Марфа Геннадьевна совершила прыжок с парашютом. Как говорится, годы летят...

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

Здесь , где e = 2.71828... — постоянная Эйлера, H — начальная высота, g = 9.8 м/с² — ускорение свободного падения, m — масса Марфы Геннадьевны. Марфа Геннадьевна пренебрегла начальной горизонтальной скоростью за счет движения самолета и приняла начальную вертикальную скорость равной 0.

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

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

Входной файл содержит вещественные числа H h_*  m k.

H и h_* заданы в км, m в кг, k в кг/с.

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

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

Ограничения

2 ≤ H ≤ 100, 1 ≤ h_*  ≤ H.

50 ≤ m ≤ 150.

0.1 ≤ k ≤ 10.

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

3 1.5 85 1

18.1178

20 12 92 0.5

41.9407