Перебор с отсечением


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 53943. Метро
Темы: Перебор с отсечением    Способы задания графа   

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

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

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

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

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

Формат входных данных
В первой строке содержится число \(k\) — количество линий метро в городе (\(1 \le k \le 10\)). Все линии пронумерованы от 0 до \(k - 1\), кольцевая линия имеет номер 0. Во второй строке записано число \(n\) — количество пересадочных станций. Каждая из следующих \(n\) строк описывает линии, пересекающиеся на соответствующей пересадочной станции, причем сначала следуют описания пересадочных станций, расположенных на кольцевой линии, в порядке их расположения на ней. Описание каждого узла начинается с количества пересекающихся в нем линий, затем следуют номера линий.

Формат выходных данных
Выведите слово YES, если по описанию можно построить схему метро, и NO в противном случае.

 
ID 55093. Шахматный детектив
Темы: Перебор с отсечением    Динамическое программирование: два параметра   

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

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

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

 

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

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

Формат входных данных
Первая строка содержит два целых числа: \(m\) и \(n\) — размеры фрагмента фотографии в пикселях (\(1 \le m, n \le 250\)).

Следующие \(m\) строк содержат по \(n\) символов каждая, \(j\)-й символ \(i\)-й строки соответствует пикселю с координатами \((i, j)\). Символ <<.>> (точка) означает белый пиксель, символ <<*>> — черный, символ <<?>> — серый.

Формат выходных данных
Если заданный фрагмент фотографии может быть изображением части шахматной доски, выведите слово <<YES>>. После этого выведите \(m\) строк по \(n\) символов в каждой. Они должны содержать изображение соответствующей части шахматной доски в том же формате, что и во входных данных, только серые пиксели должны быть заменены на белые или черные. Если решений несколько, выведите любое.

В противном случае выведите слово <<NO>>.
ID 54301. Захват королевства
Темы: Перебор с отсечением   

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

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

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

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

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

Входные данные
В первой строке вводятся целые числа N и K ( 2≤N≤256, 2k ≥ N, K≤N).

Следующие N строк содержат по N целых чисел каждая. На i-ой позиции i-ой из этих строк расположено число 0, которое означает, что город не соединен дорогой сам с собой. Для всех j≠i число на j-ой позиции i-ой из этих строк равно 1, если i-ый город соединен с j-ым белой дорогой, и равно 2, если они соединены черной дорогой. Числа в строках разделены пробелами.

Гарантируется, что входные данные корректны, то есть если i-ый город соединен с j-ым белой дорогой, то и j-ый соединен с i-ым белой дорогой, аналогично в случае черных дорог.

Выходные данные
Если захватить королевство при заданных условиях невозможно, выведите единственное число 0. В противном случае в первой строке выведите 1, если удастся захватить королевство с использованием светлых магов, и 2, если требуется использовать черных магов. В следующей строке выведите число L≤K – количество использованных магов. Третья строка должна содержать L целых чисел – номера городов, в которые следует направить магов. Заметьте, что вам не требуется минимизировать L. Если решений несколько, выведите любое.
ID 55159. Сумма произведений
Темы: Перебор с отсечением   

Дан набор переменных x1, x2, ..., xN. Каждая переменная xi может принимать значение только -1, 0 или +1. Для данного целого числа S требуется определить количество способов присвоить переменным xi значения так, чтобы сумма всех возможных произведений xi * xj была равна S, где i < j и i, j = 1, 2, ..., N. Два способа считаются различными, если они содержат различное число xi = 0.

Ограничения: 2 <= N <= 10 000, -10 000 < S < 10 000.

Входные данные
В первой строке находятся числа N и S, разделённые пробелом.

Выходные данные
Вывести одно целое число - количество способов представить S как сумму произведений.