Известный частный сыщик поставил чашку с чаем на специальную подогревающую подставку, питающуюся от USB-порта его компьютера, и приступил к обдумыванию очередного запутанного преступления. Через пару часов раздумий он понял, что для разгадки этого дела достаточно определить, была ли на месте преступления шахматная доска.

Недавно он получил по электронной почте фотографию места преступления. Подозрительный фрагмент (тот, на котором изображен предмет, похожий на шахматную доску) уже был скопирован в отдельный файл, но вдруг выяснилось, что, поскольку фотография была сжата с потерей качества, некоторые пиксели на ней из белых или черных стали серыми. Таким образом, определение того, является ли сфотографированный предмет шахматной доской, стало намного более сложным.

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

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

Шахматная доска – это квадрат, разбитый на x² (для некоторого x) равных квадратов – полей. Стороны полей параллельны сторонам изображения. Длина стороны каждого поля шахматной доски выражается целым числом пикселей. Все пиксели, принадлежащие одному полю, покрашены в один и тот же цвет – черный или белый. При этом соседние поля (поля, имеющие общую сторону) покрашены в различные цвета.

Женя получил письмо от Леши со словесным описанием схемы метро в его городе. Метро содержит одну кольцевую линию. Каждая из остальных линий пересекается с кольцевой не более, чем в двух местах, причем в точках пересечения организованы пересадочные станции. В одном месте кольцевую линию могут пересекать сразу несколько линий, имеющих общую пересадочную станцию.

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

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

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

На рисунке приведена возможная схема метро, соответствующая второму примеру.

В одном магическом королевстве есть \(N\) городов, каждые два из которых соединены дорогой. Эти дороги были построены в давние времена Светлыми и Темными силами. Дороги, которые были построены Светлыми силами, вымощены белыми камнями, а те, что построены Темными – черными. Поскольку магические чары охраняют дороги, ни одно доброе существо не может пройти по дороге, вымощенной черными камнями, и ни одно злое – по белой дороге.

Когда-то давно люди решили избрать своих правителей и изгнали верховных магов из королевства. Однако недавно верховные маги Светлых и Темных сил договорились вернуть королевство под свой контроль. Для этого они хотят направить в некоторые города королевства магов, которые возьмут эти и смежные с ними города под свой контроль.

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

Однако, при разработке плана захвата обнаружилось две трудности. Во-первых, выяснилось, что маг согласен принять участие в операции только если все маги, которые будут направлены в королевство, будут представлять ту же силу, что и он. То есть либо все участвующие в захвате маги должны быть светлыми, либо все они должны быть темными. Во-вторых, общее число магов, которые могут быть направлены в королевство не должно превышать K. Единственная надежда верховных магов заключается в том, что K достаточно велико, \(2^K\) >= \(N\).

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

«Что за свинья прошла здесь - корова, что ли?»

Под дворцом царя Миноса размером NxM построен одноэтажный лабиринт размером NxMx1. Некоторые из кубов 1x1x1 в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте S. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.

К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма «Минос, минотавр and Co» закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры 1хS.

Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина (разрезы разрешается делать только параллельно стороне рулона, имеющей длину 1).

Напишите программу, вычисляющую это минимальное число разрезов.