Хранители в опасности, и Доктор Манхэттен со своим другом Дэниелом Драйбергом должны срочно их предупредить. Всего в команде хранителей n человек, i -й из которых находится в точке плоскости с координатами ( x _i , y _i ) .

Как всем известно, доктор Манхэттен вычисляет расстояние между двумя хранителями i и j по формуле | x _i - x _j | + | y _i - y _j | . Дэниел, как обычный человек, считает, что расстояние равно .

Сейчас успех операции зависит от того, сколько существует пар ( i , j ) ( 1 ≤ i < j ≤ n ), таких что расстояние между хранителем i и хранителем j , вычисленное Доктором Манхэттеном, равняется расстоянию между ними, вычисленному Дэниелом. Вычислить эту величину попросили именно вас.

Петя увлёкся алгоритмами сжатия данных. Он уже изучил форматы gz , bz , zip и несколько других. Воодушевившись новыми знаниями, Петя собрался разработать свой формат сжатия и назвать его dis .

Петя решил сжимать таблицы. У него есть таблица, состоящая из n строк и m столбцов, заполненная целыми положительными числами. Он хочет заменить значения элементов таблицы на целые положительные числа так, чтобы отношение элементов в каждой строке и каждом столбце не изменилось. То есть, если в некоторой строке исходной таблицы a _{i , j} < a _{i , k} , то и в сжатой таблице a ' _{i , j} < a ' _{i , k} , и если a _{i , j} = a _{i , k} , то a ' _{i , j} = a ' _{i , k} . Аналогично, если в некотором столбце исходной таблицы a _{i , j} < a _{p , j} , то и в сжатой таблице a ' _{i , j} < a ' _{p , j} , и если a _{i , j} = a _{p , j} , то a ' _{i , j} = a ' _{p , j} .

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

В теории Петя мастер, но вот писать код он не любит. Помогите ему реализовать формат сжатия dis .

У компании BigData Inc. есть n дата-центров, пронумерованных от 1 до n , расположенных по всему миру. В этих дата-центрах хранятся данные клиентов компании (как можно догадаться из названия — большие данные!)

Основой предлагаемых компанией BigData Inc. услуг является гарантия возможности работы с пользовательскими данными даже при условии выхода какого-либо из дата-центров компании из доступности. Подобная гарантия достигается путём использования двойной репликации данных. Двойная репликация — это подход, при котором любые данные хранятся в двух идентичных копиях в двух различных дата-центрах.

Про каждого из m клиентов компании известны номера двух различных дата-центров c _{i , 1} и c _{i , 2} , в которых хранятся его данные.

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

Обновление дата-центра, состоящего из множества компьютеров, является сложной и длительной задачей, поэтому для каждого дата-центра выделен временной интервал длиной в час, в течение которого компьютеры дата-центра обновляются и, как следствие, могут быть недоступны. Будем считать, что в сутках h часов. Таким образом, для каждого дата-центра зафиксировано целое число u _j ( 0 ≤ u _j ≤ h - 1 ), обозначающее номер часа в сутках, в течение которого j -й дата-центр недоступен в связи с плановым обновлением.

Из всего вышесказанного следует, что для любого клиента должны выполняться условия u _{c i , 1} ≠ u _{c i , 2} , так как иначе во время одновременного обновления обоих дата-центров, компания будет не в состоянии обеспечить клиенту доступ к его данным.

В связи с переводом часов в разных странах и городах мира, время обновления в некоторых дата-центрах может сдвинуться на один час вперёд. Для подготовки к непредвиденным ситуациям руководство компании хочет провести учения, в ходе которых будет выбрано некоторое непустое подмножество дата-центров, и время обновления каждого из них будет сдвинуто на один час позже внутри суток (то есть, если u _j = h - 1 , то новым часом обновления будет 0 , иначе новым часом обновления станет u _j + 1 ). При этом учения не должны нарушать гарантии доступности, то есть, после смены графика обновления должно по-прежнему выполняться условие, что данные любого клиента доступны хотя бы в одном экземпляре в любой час.

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

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

Будем называть последовательность, состоящую из целых положительных чисел, корректной , если первое число в этой последовательности является минимальным, а последнее — максимальным. Например, последовательности [1, 3, 2, 4] и [1, 2, 1, 2] являются корректными, а последовательность [1, 3, 2] — нет.

Задана последовательность [ a ₁ , a ₂ , ..., a _n ] . Будем называть отрезок элементов заданной последовательности [ a _l , a _{l + 1} , ..., a _r ] корректным, если он представляет собой корректную последовательность: a _l является минимальным числом на этом отрезке, а a _r — максимальным.

В рамках исследования необходимо разбить заданную последовательность на минимальное количество непересекающихся корректных отрезков. Например, последовательность [2, 3, 1, 1, 5, 1] можно разбить на три корректных отрезка: [2, 3] и [1, 1, 5] и [1] .

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

У Маши есть три палочки длиной \(a\), \(b\) и \(c\) сантиметров. За одну минуту Маша может увеличить длину любой из палочек на один сантиметр. Ломать палочки не разрешается.

За какое минимальное время Маша сможет собрать треугольник положительной площади, сторонами которого будут палочки, если концы палочек должны быть вершинами треугольника?