Артур принимает участие в телешоу, в котором участникам необходимо выполнять различные интеллектуальные и физические задания, чтобы зарабатывать очки. В одном из таких заданий Артуру необходимо спасти маленького котенка.
Поле для выполнения задания представляет собой прямоугольник размером \(n \times m\) метров, разбитый на квадраты единичной площади. В одном из квадратов исходно находится Артур, в некотором другом квадрате находится котенок. Кроме того, один из квадратов содержит лифт, встав на который вместе с котенком, Артур успешно выполняет задание.
За один шаг Артур может перемещаться на любой квадрат, имеющий общую сторону с тем, на котором он стоит. После этого квадрат, на котором перед этим шагом стоял Артур, исчезает и больше на него вставать нельзя. Таким образом исчезают в том числе и квадрат, на котором исходно стоял Артур, и квадрат с котенком. Цель Артура - дойти до котенка, взять его и затем дойти до лифта. При этом очки за выполнение задания, зависят от числа шагов, которое сделает Артур, поэтому ему необходимо сделать минимальное число шагов.
Выяснив, сколько шагов ему придется сделать, Артур заинтересовался, сколько существует различных способов дойти до котенка, а затем с ним до лифта, сделав в сумме минимальное число шагов. Помогите ему это выяснить. Это число может быть довольно большим, поэтому Артур просит найти его по модулю \(10^9+7\).
Первая строка входного файла содержит два натуральных числа \(n\) и \(m\) - размеры поля для выполнения задания (\(2 \le n, m \le 100\)).
Вторая строка содержит два целых числа \(x_A\) и \(y_A\) - координаты квадрата, на котором исходно находится Артур (\(1 \le x_A \le n\), \(1 \le y_A \le m\)). Третья строка содержит два целых числа \(x_K\) и \(y_K\) - координаты квадрата, на котором сидит котенок (\(1 \le x_K \le n\), \(1 \le y_K \le m\)). Четвертая строка содержит два целых числа \(x_E\) и \(y_E\) - координаты квадрата, на котором находится лифт (\(1 \le x_E \le n\), \(1 \le y_E \le m\)). Эти три квадрата попарно различны.
В единственной строке выходного файла выведите одно число - число способов дойти до котенка и затем до лифта, не наступая на один квадрат два раза, совершив при этом минимальное количество шагов. Число необходимо вывести по модулю \(10^9+7\).
Два способа для поля, приведенного в примере.
3 3 1 1 3 3 2 2
2
В одном городе люди постоянно жаловались на то, что им мешают спать. Каждый день у соответствующих чиновников собиралась большая куча заявлений о слишком громком поведении некоторых людей ночью. С этим необходимо было что-то делать. Тогда на очередном собрании было решено принять закон, который запрещает издавать громкие звуки после одиннадцати часов вечера.
В соответствии с бюрократическими традициями, закон должен содержать расшифровку понятия <<громкий звук>>. В результате обсуждения, ночью решили запретить, например, играть на музыкальных инструментах, передвигать мебель, забивать гвозди.
Когда закон уже собирались принимать, один депутат заметил, что холодильник не является мебелью, и его перемещение не попадает под действие закона. Другие депутаты также начали придумывать дополнительные запреты, которые исходно не попали в закон. В результате были запрещены ночные стоны, скрипы, лай собак и топот котов.
За нарушение закона был введен штраф в размере \(a\) рублей.
Узнав о законе, Петя решил выяснить, какой штраф может быть наложен на жильцов его дома. Дом, в котором живет Петя, имеет \(n\) этажей, на каждом этаже находится по \(m\) квартир. Квартиры в доме пронумерованы от 1 до \(nm\). Если на некотором не последнем этаже находится квартира номер \(x\), то непосредственно над ней расположена квартира номер \(x + m\).
Известно, что в \(i\)-й квартире живет \(b_i\) котов. Петя предположил, что жильцы некоторой квартиры будут жаловаться на соседей сверху только в том случае, если коты сверху топают существенно громче, чем их собственные. Проведя эксперименты, Петя решил, что \(p\) котов топают существенно громче, чем \(q\) котов, если \(p > 2q\).
Выясните, какой суммарный штраф придется заплатить жильцам этого дома, если все, у кого коты в квартире непосредственно сверху топают существенно громче, чем их собственные коты, пожалуются на своих соседей сверху и на тех будет наложен штраф.
Первая строка входного файла содержит три целых числа \(n\), \(m\), \(a\) - количество этажей, количество квартир на каждом этаже и размер штрафа (\(1 \le n \le 20\), \(1 \le m \le 10\), \(1 \le a \le 1000\)). В следующей строке содержится \(nm\) целых чисел \(b_1, b_2, \ldots, b_{nm}\), где \(b_i\) - количество котов в \(i\)-й квартире (\(1 \le b_i \le 30\)).
Выведите в выходной файл искомый суммарный штраф.
В примере штраф придется заплатить только жильцам 6-й квартиры.
2 3 10 3 5 2 4 10 5
10
В одной стране есть странный город. В этом городе есть \(n\) перекрестков и \(m\) улиц. Каждая улица соединяет ровно два различных перекрестка и по каждой улице можно двигаться в обоих направлениях.
Однажды с целью борьбы с пробками мэр города решил провести дорожную реформу. Он решил запретить автомобильное движение на некоторых улицах и сделать их пешеходными. При этом исследования департамента транспорта показали, что результаты реформы будут оптимальными, если после ее осуществления из каждого перекрестка будет выходить нечетное число улиц, на которых разрешено автомобильное движение.
Подчиненные мэра озадачены. Они никак не могут исполнить приказ мэра. Вам предлагается сделать это за них. Вам задана карта города, требуется решить, какие улицы необходимо сделать пешеходными, а какие - оставить для автомобилей, чтобы в результате реформы из каждого перекрестка выходило нечетное число улиц, по которым разрешено движение автомобилей.
В первой строке заданы целые числа \(n\) и \(m\) (\(1 \le n \le 2 \cdot 10^5\), \(0 \le m \le 2 \cdot 10^5\)) - количество перекрестков и количество дорог в городе соответственно.
В следующих \(m\) строках заданы дороги, каждая дорога описана в отдельной строке. В \((i+1)\)-й строке описывается дорога с номером \(i\). Каждая дорога задается двумя целыми числами \(v\) и \(u\) - номерами двух перекрестков, которые эта дорога соединяет (\(1 \le v, u \le n\)).
Гарантируется, что дорога не соединяет перекресток с самим собой.
Гарантируется, что любая пара перекрестков соединена не более чем одной дорогой.
Не гарантируется, что от исходно любого перекрестка можно добраться до любого другого по улицам.
Если удовлетворить условие в приказе мэра невозможно, выведите единственное число \(-1\) в первой строке выходного файла.
Иначе в первой строке выведите число \(k\) - количество дорог, которые нужно оставить для автомобильного движения. В следующей строке выведите \(k\) различных чисел через пробел - номера этих дорог. Дороги пронумерованы от 1 до \(m\) в том порядке, в котором они заданы во входном файле.
2 1 1 2
1 1
4 4 1 2 2 3 3 4 4 1
2 2 4
Раз, два, левой, правой
дважды два - очень просто
измеряются удавы
пятью пять - любого роста
Попугай
После того, как Мартышка и Попугай досконально исследовали длину Удава, им стало очень скучно. Тут Слоненок вспомнил, что в лесу живет еще Питон, которого тоже можно измерять! Друзья сразу же отправились на его поиски.
Питон, как и Удав, тоже целый, поэтому его нельзя мерить половинками. Измерив Питона, Мартышка и Попугай узнали, что в Питоне помещается \(n\) целых Попугаев или \(m\) целых Мартышек. Обрадованная Мартышка убежала сообщить полученный результат Слоненку. Когда она ушла, Попугая заинтересовал следующий вопрос: а сколько раз он помещается в одной Мартышке?
Так как Мартышка убежала, и измерить ее он не может, Попугай решил попытаться выяснить, сколько целых Попугаев может поместиться в одной Мартышку, используя результаты измерения Питона. По заданным \(n\) и \(m\) выясните, какое минимальное и максимальное число целых Попугаев может помещаться в одной Мартышке.
Во входном файле заданы два целых числа \(n\) и \(m\), каждое на своей строке - количество
Попугаев и Мартышек в Питоне, соответственно
(\(1 \le n, m \le 10^9\)).
В выходной файл выведите два числа - минимальное и максимальное количество целых Попугаев в одной Мартышке.
38 5
6 7
Первокурсник Рома приехал в общежитие и, удивившись беспорядку в комнате и толстому слою пыли на полу, начал наводить порядок. Первым делом он решил вымыть пол. Для этого Рома в магазине приобрел инновационную швабру.
Изначально моющая часть швабры имела идеальную прямоугольную форму, но в процессе перевозки из магазина в общежитие у нее отломился один из углов. Таким образом, теперь она представляет собой многоугольник, граница которого состоит из двух соседних сторон прямоугольника, фрагментов двух оставшихся сторон и ломаной, соединяющей концы этих фрагментов.
Рома живет в большой прямоугольной комнате. Рома провел сломанной шваброй от одной стороны комнаты до другой, не отрывая ее от стены, так что в результате отломанный угол швабры оказался в углу комнаты. При этом часть соответствующей прямоугольной полосы пола в углу осталась невымытой.
Рома считает, что все точки, в которых в какой-то момент находилась моющая часть швабры оказались вымыты. Теперь он решил выяснить, какая часть этой полосы осталась грязной.
Помогите ему вычислить площадь этой части. Можете считать, что размер комнаты, в которой живет Рома, существенно больше размеров моющей части швабры.
Первая строка входного файла содержит два целых числа \(w\) и \(h\) - размеры моющей части швабры до повреждения (\(2 \le w, h \le 10^5\)).
Вторая строка содержит целое число \(n\) - число вершин ломаной, соединяющей соседние стороны швабры (\(2 \le n \le 10^5\)). В \(i\)-й из следующих \(n\) строк заданы два целых числа \(x_i\) и \(y_i\) (\(1 \le x_i < w\), \(1 \le y_i < h\), за исключением \(y_1 = h\), \(x_n = w\)) - координаты \(i\)-й вершины ломаной. Ломаная не имеет самопересечений и самокасаний.
Координаты введены таким образом, что стена, вдоль которой Рома провел шваброй, соответствует прямой \(y=h\).
В выходной файл выведите площадь невымытой части пола с абсолютной или относительной погрешностью не более \(10^{-6}\). Это значит, что если правильный ответ \(a\), а вы вывели \(p\), то ваш ответ будет засчитан как правильный, если \(\frac{|a-p|}{\max(|a|, 1)}\le 10^{-6}\).
9 7 9 3 7 4 5 5 6 4 4 5 2 6 4 7 2 8 3 9 2
18.0