Перебор

Однако, ФД сможет восстановить перестановку, которую он изначально выписал. Перед тем, как листок с перестановкой был украден, Беси выписала последовательность \(b_1,b_2,\ldots,b_{N-1}\) такую, что \(b_i=a_i+a_{i+1}\) для всех \(1\le i<N.\)

Основываясь на информации от Беси, помогите ФД восстановить "лексикографически минимальную" перестановку \(a\), которая может произвести \(b\). Перестановка \(x\) лексикографически меньше перестановки \(y\), если для некоторого \(j\), \(x_i=y_i\) для всех \(i<j\) и \(x_j<y_j\) (другими словами, две перестановки идентичны до определённой точки, в которой \(x\) меньше чем \(y\)). Гарантируется, что существует как минимум одна такая перестановка \(a\)

Беси знает \(N\) (\(1 \leq N \leq 5000\)) слов и хочет организовать их в поэму. Она определила длину в слогах каждого слова, кроме того она распределила их в "классы рифм". Каждое слово рифмуется только с другими словами из этого же класса рифм.

Каждая из поэм Беси включает \(M\) строк (\(1 \leq M \leq 10^5\)) и каждая строка должна состоять из \(K\) (\(1 \leq K \leq 5000\)) слогов. Более того, поэм Беси должна соответствовать специфической схеме рифм.

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

Сначала Беси задумывает некоторое животное. Затем Эльза задаёт серию вопросов, чтобы угадать, какое животное задумала Беси. На каждый вопрос Беси отвечает "Да" или "Нет". Например:

Эльза: "Животное летает?" 
Беси: "Нет" 
Эльза: "Ест траву" 
Беси: "Да" 
Эльза: "Даёт молоко?"
Беси: "Да" 
Эльза: "Делает му-у?"
Беси: "Да" 
Эльза: "Корова." 
Беси: "Точно!"

Назовём "правдоподобным множеством" множество всех всех животных, с характеристиками подходящими вопросам Эльзы. Эльза задаёт вопросы пока в "правдоподобном множестве" останется только одно животное, после чего она называет его в качестве ответа. Для каждого вопроса Эльза выбирает характеристику некоторого животного и спрашивает о ней (даже если ответ не сузит "правдоподобное множество"). Она никогда не спрашивает об одной и той же характеристике дважды.

Вам даны все животные, которых знают Беси и Эльза и их характеристики. Определите максимальное количество ответов "Да", которые может получить Эльза, прежде чем она узнает задуманное животное.

К несчастью, коровы довольно разборчивы и требуют, чтобы ФД доил их в порядке, который соответствует \(N\) ограничениям (\(1 \leq N \leq 7\)). Каждое из ограничений имеет вид "\(X\) must be milked beside \(Y\)" ("\(X\) необходимо подоить рядом \(Y\)"), что означает, что в порядке дойки корову \(X\) нужно доить сразу после коровы \(Y\) или непосредственно перед коровой \(Y\).

Пожалуйста, помогите ФД определить порядок дойки его коров, который удовлетворяет всем требуемым ограничениям. Гарантируется, что такое упорядочивание всегда возможно. Если возможно несколько упорядочиваний, выведите первое из них в алфавитном порядке. То есть, первая корова должна иметь наименьшее в алфавитном порядке имя из всех возможных имён, которые могут быть первыми. Среди всех упорядочиваний, начинающихся с этой же первой коровы, вторая корова должна быть наименьшей в алфавитном порядке среди всех корректных упорядочиваний и т.д.

Сцена для шоу представляет \(N\) платформ, размещённых по кругу. На каждой платформе от \(1\) до \(N\) коров формируют стек (корова становится на корову). По сигналу главного на манеже, все стеки параллельно "падают" по часовой стрелке так, что нижняя корова стека не движется, корова на ней движется на одну платформу по часовой стрелке, следующая корова - на две платформы и т.д. В результате получаются новые стеки коров.

Главный на манеже думает, что шоу будет лучше, если после того, как стеки упадут, новый стек на каждой платформе будет содержать такое же количество коров, что и исходный стек на манеже. Мы называем конфигурацию стеков на манеже "магической", если она удовлетворяет этому условию. Вычислите количество "магических" конфигураций. Поскольку это число может быть очень большое, выведите его остаток по модулю \(10^9 + 7\).

Две конфигурации считаются различными, если существует платформа, для которых у этих двух конфигураций различное количество коров.

В понедельник ФД отмерял ровно \(1000\) галлонов молока в цистерну первого амбара, и ровно \(1000\) галлонов молока в цистерну второго амбара.

Во вторник он берёт бидон из первого амбара, наполняет его и переносит во второй амбар, где выливает это молоко в цистерну, а бидон оставляет во втором амбаре.

В среду он берёт бидон из второго амбара (возможно, тот, который он оставил во вторник), наполняет его, переносит молоко в первый амбар и выливает его в цистерну первого амбара. Он оставляет бидон в первом амбаре.

В четверг он берёт бидон из первого амбара (возможно тот, который оставил в среду), наполняет его и переносит во второй амбар, где выливает это молоко в цистерну, а бидон оставляет во втором амбаре.

В пятницу он берёт бидон из второго амбара (возможно, тот, который он оставил во вторник ил четверг), наполняет его, переносит молоко в первый амбар и выливает его в цистерну первого амбара. Он оставляет бидон в первом амбаре.

ФД измеряет молоко в цистерне первого амбара. Сколько возможных вариантов такого измерения он может увидеть?

Форма этой коровы описывается решёткой из \(N \times N\) символов (\(3 \leq N \leq 8\)), пример показан ниже, где символы '#' представляют часть коровы, а символы '.' не части коровы.

...............
...............
...............
#..#...........
####...........
############...
.##.#########..
....#######.##.
....##...##....
....##...##....
...............
...............
...............
...............
...............

К несчастью, ФД ещё не спел купить корову, как в магазинчик ворвался бык, который поломал всё вокруг, включая корову ФД. Корова разломалась на две части, которые затерялись среди других \(K\) (\(3 \leq K \leq 10\)) кусков стекла на полу. Каждый из этих \(K\) кусков описывается решёткой \(N \times N\) символов, как и исходная фигурка.

Помогите ФД определить, какие из этих \(K\) кусков являются двумя частями фигурки ФД. При падении на землю куски ФД не поворачивались и не переворачивались, поэтому для их сборки ФД должен только сдвигать куски горизонтально или вертикально. Куски не могут наезжать друг на друга и должны сформировать точно исходную фигуру.

ФД может двигать оба куска горизонтально и/или вертикально на любое количество позиций, но так, чтобы все символы '#' оставались внутри решётки \(N \times N\). Форма каждого из кусков необязательно состоит из связного региона символов '#'. Но при сдвиге все они сдвигаются на одинаковое количество позиций.