Задача A. Tower Defence ≡

Условие

Юный супергерой Вася однажды выяснил, что на один из небоскрёбов его города (состоящий из M этажей, пронумерованных от 1 до M) планирует напасть группа из N злодеев. Вася прибыл на первый этаж непосредственно перед началом нападения злодеев и приготовился его отражать.

Злодей номер i появляется на этаже f_i через t_i секунд после начала нападения, и начинает творить зло со скоростью одно злое дело в секунду.

Каждую секунду Вася проделывает следующие действия:

1. Если на текущем этаже находятся злодеи, обезвреживает их.
2. Сдвигается вниз или вверх на один этаж по направлению к ближайшему злодею.
3. Если расстояния равны, Вася предпочитает подниматься вверх.
4. Если в текущий момент ни одного активного злодея в небоскрёбе нет, Вася остаётся на текущем этаже.

Требуется определить, сколько злых дел успеют совершить все злодеи в сумме.

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁶;

1 ≤ f_i ≤ M ≤ 10⁹;

1 ≤ t_i ≤ t_i + 1 ≤ 10⁹;

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

3 3
1 2
2 3
5 1

4

100 1
1 100

99

1 1
1 1

0

Задача B. Синхронизация ≡

Условие

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

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

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

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

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

Входной файл содержит целое число N. Далее следует N целых чисел a₁, a₂, …, a_N — времена событий, зафиксированных коллайдером. Затем записано целое число M. Далее следует M чисел b₁, b₂, …, b_M — времена событий, зафиксированных Колей.

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

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

Ограничения

2 ≤ M ≤ N ≤ 10⁵;

0 ≤ a₁ ≤ a₂ ≤ …  ≤ a_N ≤ 10⁹;

0 = b₁ ≤ b₂ ≤ …  ≤ b_M ≤ 10⁹;

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

5
10 15 17 19 20
2
0 2 

2

Задача C. Система зеркал ≡

Условие

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

Юные физики изучают лучи солнечного света, которые, падая на первое зеркало, отражаются от него, затем падают на второе зеркало и отражаются от него, затем падают на третье зеркало и т.д. Лучи света, идущие, например, от первого зеркала сразу к третьему зеркалу, не рассматриваются.

Так как Солнце находится на достаточно большом расстоянии от Земли, при расчётах часто считают Солнце бесконечно удалённой точкой. В этом случае световые лучи, испускаемые Солнцем, считают параллельными друг другу.

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

Пусть зеркала наклонены так, что в некоторой системе координат их можно задать как прямые, имеющие уравнения y = k_i x + b_i. Направление падения солнечных лучей задаётся единичным вектором a.

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

Примечание. По законам оптики, свет отражается так, что угол падения равен углу отражения (α = β на рисунке).

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

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

Вторая строка содержит вещественные числа x₁ y₁ — координаты вектора a.

Третья строка содержит N вещественных чисел k_i — угловые коэффициенты прямых.

Длина вектора a приближённо равна 1.

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

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

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

Длина вектора c должна быть приближённо равна 1.

Координаты вектора c должны быть выведены с точностью до 3-х знаков после запятой.

Ограничения

1 ≤ N ≤ 10

 − 1000 ≤ k_i ≤ 1000

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

1
0.7071067812 -0.7071067812
0

0.7071067812 0.7071067812

1
1 0
1

0 1

2
1 0
1 -1

-1 0