#113805

Тетрис

Темы: [Применение обхода в глубину] [Разбор случаев]

Ивица — страстный компьютерщик. Недавно он начал работать над своей первой компьютерной игрой — клоном популярного тетриса. Хотя игра далека от завершения, его программа уже поддерживает размещение в матрице N × M пяти разных фигур Тетриса (показанных на изображении ниже) в матрице. Перед тем, как поместить фигуру в матрицу, её можно поворачивать на 90 градусов произвольное число раз и можно окрашивать. Кроме того, текущая версия игры не поддерживает размещение фигуры, если она при этом выходит за границы матрицы или перекрывается с другими существующими фигурами в матрице.

$\text{[math]}$

Пока Ивица учился в школе, его сестра Марика начала игру и случайным образом повернула, покрасила и поместила фигуры, но таким образом, что соседние фигуры окрашены по-разному. Две фигуры смежны, если они имеют общую сторону или общий угол.

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

Входные данные

Первая строка ввода содержит положительные целые числа N и M ( 1 ≤ N , M ≤ 10 ), которые представляют количество строк и столбцов матрицы Тетриса. Каждая из следующих N строк содержит M символов, которые представляют матрицу. Каждый символ может быть « . », что означает пустую клетку или строчной буквой английского алфавита, которая представляет часть фигуры. Различные буквы представляют разные цвета, а клетки одной фигуры имеют одинаковый цвет.

Гарантируется, что вводная матрица могла быть получена последовательным добавлением фигур Тетриса в изначально пустую матрицу.

Выходные данные

Вы должны вывести ровно пять строк. i -я строка должна содержать количество фигур i -го типа, находящихся в данной матрице.

Система оценки

$\text{[math]}$

Примеры

Входные данные

4 5
aaaa.
.bb..
.bbxx
...xx

Выходные данные

Входные данные

4 5
.aab.
aabb.
.cbaa
cccaa

Выходные данные

Входные данные

5 7
.c.....
ccdddd.
caabbcc
aabbacc
...aaa.

Выходные данные

#114307

Клуб

Темы: [Паросочетания] [Применение обхода в глубину] [Эйлеров цикл]

Бойцовский клуб дебатов - необычный клуб во всех отношениях. Каждый из $2^{n}$ его членов заполнил специальную анкету, содержащую $n$ вопросов с бинарным ответом (да/нет) о своих взглядах. Ответы каждого человека могут быть представлены в виде последовательности из $n$ бит, иначе говоря в виде числа от $0$ до $2^{n} - 1$.

Перечислим ещё несколько инетерсных фактов о бойцовском клубе дебатов.

взгляды никаких двух членов клуба не совпадают, т. е. каждое из чисел от от $0$ до $2^{n} - 1$ встречается в числовых представлениях анкеты клуба
ровно половина членов клуба мужчины, остальные - женщины (т. е. и мужчин, и женщин по $2^{n - 1}$) и они формируют $2^{n - 1}$ разнополых пар
два члена клуба считаются близкими по взглядам тогда, и только тогда когда у них в анкете отличается ответы ровно на один вопрос (иначе говоря, $a_i \oplus b_i = 2^k$ для некоторого $k$, где $a_i$ и $b_i$ - числа, кодирующие взгляды первого и второго человека соответственно)
во время дебатов члены клуба сидят за круглым столом
члены клуба хотят сидеть так, чтобы соеседями с одной стороны была его пара, с другой стороны, человек, близкий ему по взглядам

Входные данные

В первой строке вводится число $n$ ($2 \le n \le 18$) - количество вопросов в анкете.

В последующих $2^{n - 1}$ строках даны пары людей. В $i$ строке даны целые числа $a_i$ и $b_i$, разделённые одним пробелом - что означает, что люди, чьи анкеты закодированы числами $a_i$ и $b_i$ являются парой. Гарантируется, что каждое целое число от $0$ до $2^{n} - 1$ встретится во вводе ровно один раз.

Выходные данные

Выведете строку со единственным словом 'NO' , если не существует рассадки членов клуба по местам удоволетворяющей условию.

Иначе, выведете в первой строке слово 'YES'. Во второй строке выведите $2 ^ n$ чисел, разделённые пробелами, кодирующие ответы последовательных людей вокруг стола - корректную рассадку (стол круглый, поэтому можно начинать вывод с любого человека).

Если существует несколько решений, выведите любое.

Система оценки

В задаче оценка по подгруппам. Подгруппы отличаются значением $n$. Для для $n = 2$ - $4$ балла за подгруппу, для каждого значения $n$ от $3$ до $18$ по $6$ баллов за подгруппу.

Примеры

Входные данные

Выходные данные

YES
0 5 7 2 6 3 1 4

#114314

Туризм

Темы: [Динамическое программирование на графах] [Применение обхода в глубину]

Король Байтазар считает, что Байтотия — земля, полная красивых достопримечательностей — должна привлечь множество туристов, которые должны потратить много денег, которые в конечном счете должны найти свой путь в королевскую казну. Но реальность далека от мечты. Поэтому король поручил своему советнику изучить этот вопрос. Советник выяснило, что иностранцы держаться подальше от Байтотии из-за ее плохой дорожной сети. В Байтотии $n$ городов соединенных $m$ двусторонними дорогами. Не гарантируется, что от каждого города можно добраться от любого другого города. Советник отметил, что нынешний дорожная сеть не позволяет делать длительные путешествия. А именно, где бы вы не начали поездку, невозможно посетить более 10 городов не прохождения через какой-то город два раза. Из-за ограниченных средств в казне, новые дороги построить нельзя. Вместо этого, Байтазар решил создать сеть туристическо-информационных пунктов (ТИП), которые будут рекламировать короткие путешествия. Для каждого города должен быть ТИП либо в нем, либо в одном из городов, непосредственно связанных с ним дорогой. Кроме того, известна стоимость строительства ТИПа в каждом из городов. Помогите королю найти самый дешевый спосою построить ТИПы, так, чтобы это условие удовлетворялось.

Входные данные

Первая строка стандартного ввода содержит два целых числа $n$ и $m$ ($2 \le n \le 20000, 0 \le m \le 25000$), которые задают количество городов и дорог в Байтотии соответственно. Города нумеруются от $1$ до $n$. Вторая строка содержит целые числа $c_i$ ($0 \le ci \le 10000$) — стоимости строительства ТИПов в городах. Затем идет описание дорожной сети. i-я строка содержит два целых числа $a_i, b_i$, которые указывают, что города $a_i$ и $b_i$ связаны дорогой. Существует не более одной дороги между любой парой городов.

Выходные данные

Выведите одно целое число — общую стоимость строительства всех ТИПов.

Система оценки

Подзадача 1 (22 балла): $1 \le n, m \le 20$

Подзадача 2 (78 баллов): Без дополнительных ограничений. Оценивается потестово. (6 баллов за тест)

Примеры

Входные данные

6 6
3 8 5 6 2 2
1 2
2 3
1 3
3 4
4 5
4 6

Выходные данные