Задача A. Черно-белая графика ≡

Условие

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

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

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

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

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

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

Ограничения

1 ≤ w, h ≤ 100

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

5 3
01000
11110
01000
10110
00010
10110
0110

11110
11100
11110

Задача B. Газон Ивана ≡

Условие

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x₁, y₁) и (x₂, y₂). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x₃, y₃) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x₃, y₃) не превышало r.

Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

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

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

В первой строке входного файла содержатся четыре целых числа x₁ y₁ x₂ y₂. Во второй строке входного файла содержатся три целых числа x₃ y₃ r.

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

Ограничения

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

1 ≤ r ≤ 10⁵

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

0 0 5 4
4 0 3

14

Задача C. Пассажиры трамвая ≡

Условие

С окраины в центр города каждое утро по одному маршруту едут в трамвае N человек. За долгое время поездок они достаточно хорошо узнали друг друга. Чтобы никому не было обидно, они захотели решить, кто из них и между какими остановками маршрута должен сидеть, а кто должен стоять. Все остановки пронумерованы от 1 до P.

Один из пассажиров оказался знатоком теории математического моделирования. Он предложил рассмотреть значение суммарного удовлетворения пассажиров. Для каждого i-го пассажира он оценил две величины — a_i и b_i. Если в течение одного переезда между остановками пассажир сидит, то к суммарному удовлетворению прибавляется a_i, если же он стоит, то прибавляется b_i.

Всего в трамвае M сидячих мест. Вставать и садиться пассажиры могут мгновенно на любой остановке. Кроме того, некоторые пассажиры предпочитают ехать стоя, даже если в трамвае есть свободные места (для них a_i < b_i).

Требуется написать программу, которая вычисляет значение максимально достижимого суммарного удовлетворения, если для каждого i-го пассажира известны величины a_i и b_i, а также номера остановок, на которых он садится и выходит из трамвая.

В примере максимум достигается следующим образом: на 1-й остановке входят и садятся второй и третий пассажиры; на 2-й остановке входят первый и четвертый пассажиры, второй уступает место первому; на 3-й остановке встают и выходят первый и третий пассажиры, второй и четвертый садятся на их места; на 4-й остановке выходят второй и четвертый пассажиры.

За прохождение всех тестов с P ≤ 100 решение получит 80 баллов, за прохождение всех тестов с N, M, P ≤ 100 — 60 баллов.

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

Первая строка входного файла содержит три целых числа N M P — число пассажиров, число сидячих мест и число остановок на маршруте соответственно.

Каждая из следующих N строк содержит информацию об очередном пассажире в виде четырех целых чисел a_i b_i c_i d_i, где первые два числа определяют вклад в суммарное удовлетворение, третье — номер остановки, на которой пассажир садится в трамвай, и последнее — номер остановки, на которой он выходит из трамвая (1 ≤ c_i < d_i ≤ P).

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

Ограничения

1 ≤ N, M ≤ 10⁵; 2 ≤ P ≤ 10⁵;  − 10⁶ ≤ a_i, b_i ≤ 10⁶

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

4 2 4
10 -10 2 3
-1 -3 1 4
6 -6 1 3
7 4 2 4

28

Задача D. Равнобедренные треугольники ≡

Условие

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

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

Требуется написать программу, решающую указанную задачу.

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

Входной файл содержит в первой строке целое число n. Каждая из последующих строк содержит по два целых числа — x_i и y_i, определяющих координаты i-ой точки. Среди заданных точек нет совпадающих.

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

Ограничения

 − 10⁹ ≤ x_i, y_i ≤ 10⁹

3 ≤ n ≤ 1500

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

3
0 0
2 2
-2 2

1

4
0 0
1 1
1 0
0 1

4