Недавно археологической командой «Раскопай» были обнаружены остатки древней цивилизации. Особое внимание привлекла карта с месторасположением народов, живших в то время. Карта представляет собой прямоугольный лист, разлинованный горизонтальными линиями на M полос и вертикальными линиями на N столбцов. Таким образом формируются M*N клеток — древних поселений, которые заселялись сообществами. В каждой клетке этой карты написано натуральное число — идентификатор народа, к которому принадлежит это сообщество людей (рукопись с соответствием между идентификаторами и народами также была обнаружена).
<>Группа историков «Разузнай» имеет такую же карту, но только на тысячелетие древнее. Естественно, она может отличаться от той, которую нашли археологи — ведь за такой срок сообщества могли переселяться в другие поселения. Историками была высказана идея о механизме переселения народов.Чтобы объяснить этот процесс введем систему координат на карте так, что границы карты параллельны осям координат. Пусть координаты (0,0) соответствуют самой верхней левой клетке, а (N–1, M–1) — самой нижней правой. Переселение народов проходит в несколько этапов. Опишем как проходит каждый этап.
Назовем квадратом множество всех поселений с координатами (x,y) такими, что x1≤x≤x2, y1≤y≤y2, где x2–x1=y2–y1. Соответственно клетка (x1,y1) является левой верхней клеткой квадрата, (x2,y2) —нижней правой.
На каждом этапе переселения переселяются сообщества внутри некоторого квадрата по следующему правилу. Если переселение происходит внутри квадрата, левой верхней клеткой которого является клетка (x1,y1), а правой нижней — (x2,y2), то сообщество, проживавшее в поселении с координатами (x,y) (x1≤x≤x2, y1≤y≤y2) переселяется в поселение с координатами (x2–(y2–y),y2–(x2–x)), при этом, возможно, что некоторые сообщества остаются на своих местах. Все сообщества, живущие вне квадрата, в котором происходит переселение, остаются на своих местах.
Историки из «Разузнай» хотят для подтверждения (или опровержения) своей теории переселений проверить, могла ли в результате таких переселений из карты, которая есть в распоряжении «Разузнай» получиться карта, которую нашли археологи. Помогите им — напишите программу, которая будет это делать.
На первой строке входного файла заданы через пробел 2 натуральных числа M и N, где M — количество строк, а N — количество столбцов (1≤M≤30, 1≤N≤30). Далее описывается карта историков. После нее записана карта археологов.
Каждая карта описывается в M строках, в каждой из которых записано по N чисел — идентификаторы народов, проживающих в соответствующих поселениях. В первой строке описания записаны народы, проживающие в поселениях с координатами (0,0), (1,0), (2,0),…,(N–1,0), во второй — в поселениях (0,1), (1,1), (2,1),…,(N–1,1), в M-ой — с координатами (0, M–1), (1,M–1),…,(N–1,M–1). Идентификаторы народов — натуральные числа, не превышающие 2∙109. Некоторые идентификаторы могут не использоваться (например, на карте могут встречаться народы с номерами 1 и 3, и не встречаться народ с идентификатором 2).
Если гипотеза историков подтверждается, то в выходной файл выведите количество этапов переселения народов и дальше сами эти этапы, в результате которых из карты историков получается карта археологов. Каждый этап должен быть описан четырьмя числами — x1, y1, x2, y2 (координатами углов квадрата, который переселяется). Обратите внимание, что добиваться минимального количества переселений всех народов, или же минимального количества этапов не требуется. Важно, чтобы общее число этапов не превышало 10000 (математики из общества «Докажи» доказали, что в указанных ограничениях это всегда возможно).
Если гипотеза историков неверна, т.е. из карты историков карта археологов с помощью только таких переселений получиться не могла, то выведите в выходной файл одно число –1 (минус один).
Пояснение к примеру 1
Переселение проходит в 2 этапа: на рисунке ниже закрашены квадраты, в которых происходили переселения сообществ.
3 4 1 4 2 2 1 3 3 1 2 1 1 1 1 1 2 3 4 3 1 1 2 2 1 1
2 2 0 3 1 0 0 2 2
2 2 6 8 5 8 6 8 5 9
-1
В компании QQQ работает n человек. Очередной проект компании состоит из m независимых частей. Управляющий компании оценил время, которое требуется для выполнения каждой из частей проекта (предполагается, что это время не зависит от того, кто будет выполнять эту часть). После чего он некоторым образом распределил все m частей между n работниками. В результате оказалось, что некоторым из работников потребуется потратить на выполнение своей работы больше времени, чем другим (поскольку им досталась более объемная работа).
Поэтому управляющий решил улучшить распределение работ следующим образом: выбрать двух различных работников и выбрать одну из частей проекта, назначенную первому работнику, и одну из частей, назначенную второму. После этого часть проекта, назначенную первому работнику, назначить второму, а часть, назначенную второму, назначить первому. Если в результате этой операции максимум из времен выполнения работы первым и вторым работниками уменьшился, то такую операцию назовем оптимизирующей.
Например, пусть проект состоит из пяти частей со временами выполнения 3,6,4,8,2, и в компании есть три работника. Пусть распределение работ выглядит следующим образом: первый работник части 1 и 2 (суммарное время 3 + 6 = 9), второй работник часть 4 (суммарное время 8) и третий работник части 3 и 5 (суммарное время 4 + 2 = 6). Тогда если первое задание (назначенное первому работнику) назначить третьему, а пятое задание (назначенное третьему) назначить первому, то у первого работника суммарное время станет равно 6 + 2 = 8, а у третьего 3 + 4 = 7. Поскольку max(9,6) > max(8,7), то эта операция будет оптимизирующей.
Вам дано число работников в компании, число частей в проекте, время, необходимое на выполнение каждой из частей проекта и распределение частей по работникам. Требуется посчитать число различных возможных оптимизирующих операций в данном распределении работ.
Первая строка входного файла содержит два натуральных числа n и m (1 ≤ n,m ≤ 105) число работников в компании и число частей в проекте соответственно. Вторая строка содержит m натуральных чисел i-ое число равно времени выполнения i-ой части проекта (части проекта нумеруются, начиная с 1). Времена выполнения частей не превосходят 109. Далее идут n строк, описывающих распределение частей по работникам. Каждая строка содержит описание частей проекта, которые получил соответствующий работник. Описание состоит из числа частей, которые достались работнику, и их номеров.
В выходной файл выведите искомое число оптимизирующих операций.
3 5 3 6 4 8 2 2 1 2 1 4 2 3 5
2
5 13 1 2 7 5 8 7 5 4 1 5 1 5 7 3 1 2 3 2 4 5 2 6 7 3 8 9 10 3 11 12 13
5
«Что за свинья прошла здесь - корова, что ли?»
Под дворцом царя Миноса размером NxM построен одноэтажный лабиринт размером NxMx1. Некоторые из кубов 1x1x1 в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте S. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.
К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма «Минос, минотавр and Co» закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры 1хS.
Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина (разрезы разрешается делать только параллельно стороне рулона, имеющей длину 1).
Напишите программу, вычисляющую это минимальное число разрезов.
Во входном файле записано сначала число N, затем число M, задающие размеры лабиринта (1N10, 1M10). Далее идет N строк, по M чисел в каждой, задающих лабиринт. Каждое из этих чисел 0 или 1 — 0 означает пустой куб, а 1 — гранитный.
В выходной файл выведите одно число — минимальное возможное количество разрезов, которое нужно сделать в рулоне, чтобы застелить все пустые клетки лабиринта.
1 10 1 1 1 1 1 0 0 0 0 0
0
2 2 1 0 0 0
1
Задачи противовоздушной обороны: ...борьба с десантом на всем маршруте пролета,
уничтожение вертолетов огневой поддержки, действующих из засады»
Радиолокационная станция (РЛС) состоит из нескольких передатчиков (не более 5). К сожалению, их нельзя ставить рядом — они друг для друга создают помехи. Каждый передатчик состоит из квадратных модулей, которые располагаются вплотную друг к другу.
Вам дана карта района, в котором расположена РЛС. Вся карта для удобства разбита на квадраты, и для каждого квадрата известно, располагается в нем какой-то из модулей одного из передатчиков РЛС или нет.
Требуется оградить забором (или несколькими заборами) минимально возможной суммарной длины все передатчики РЛС. Забор — это произвольная ломаная (ее элементы не обязаны идти по сторонам клеток). Одним забором могут быть огорожены сразу несколько передатчиков.
Во входном файле записаны два числа N и M, задающие размеры района, в котором расположена РЛС (1N20, 1M20). Далее идет N строк, по M чисел в каждой, задающих карту района. Каждое из этих чисел 0 или 1 — 1 означает, что в этом квадрате находится один из модулей передатчика РЛС, а 0 — что в этом квадрате ничего ценного нет.
Общее количество передатчиков РЛС не превышает 5. Каждый передатчик — это связанная группа модулей (модули называются связанными, если они располагаются в квадратах карты, у которых есть общая граница, либо связаны через какие-то другие модули).
Ограничения на число модулей нет.
В выходной файл выведите одно число — минимально возможную длину забора с тремя значащими цифрами после точки.
2 2 1 0 0 1
6.828
4 5 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1
18.000
Известно, что в книгах для слепых для обозначения различных букв используются различные комбинации выступов, которые читающий различает на ощупь. Пусть для обозначения буквы используется прямоугольник шириной M мм и высотой N мм, причем некоторые входящие в него квадратики размера 1∙1 содержат выступ.
Поскольку слепой не видит границ прямоугольника, то он не может различить комбинации, получающиеся друг из друга сдвигом. Так, он не может различить комбинации а) и б) на рисунке 1. (В то же время комбинации а) и в) являются различимыми, поскольку не могут быть получены друг из друга сдвигом)
Рисунок 1.
Из-за этого при разработке алфавита для слепых появилась проблема: сколько различных букв можно представить с помощью выступов, если запрещается сопоставлять различным буквам комбинации, получающиеся друг из друга сдвигом. Прямоугольник совсем без выступов также нельзя использовать в качестве буквы (поскольку при написании слова между некоторыми буквами может появиться такой прямоугольник, например между а) и г) на рисунке 1).
Требуется подсчитать количество различных букв, которые можно представить таким способом, если прямоугольник имеет размер M∙N.
В качестве примера, все буквы размера 2∙2 приведены на рисунке 2. (Среди комбинаций, отвечающих одной букве, приведена только одна)
Рисунок 2.
Входной файл содержит числа M и N, разделенный пробелом. Поскольку человек одновременно не может воспринимать слишком много информации, M∙N ≤ 30.
Выведите в выходной файл единственное число – количество различных букв, которые слепой сможет различить при заданном размере прямоугольника.
2 3
44