Перебор

Кк известно, коровы - существа привычки, и они пересекают дорогу одним и тем же способом каждый день. Каждая корова входит на поле в точке, отличной от той, в которой она выходит с поля и все эти точки отличаются друг от друга. У ФД ровно 26 коров, которые лениво названы от A до Z и поэтому на поле имеется ровно 52 точки. ФД записал эти точки по часовой стрелке, записав букву - имя коровы, для которой эта точка. В результате ФД получил строку из 52 символов, в которой каждая буква алфавита встречается ровно дважды. Он не записывал, какая точка для входа, какая - для выхода.

Разглядывая свою карту точек, ФД заинтересовался, сколько раз могут пересечься пути различных пар коров. Он называет пару коров \((a,b)\) "пересекающейся" парой, если путь коровы \(a\) от входа к выходу должен пересечь путь коровы '\(b\)' от входа к выходу. Помогите ФД посчитать общее количество пересекающихся пар.

- Он может заполнить любой бидон полностью

- Он может опорожнить полностью любой бидон.

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

ФД понял, что он может и не отмерять ровно \(M\) единиц молока, в двух бидонах. Помогите ему определить минимальную разность между \(M\) и суммарным молоком в двух баллонах. То есть, определите минимальное значение \(|M-M'|\) такое, что ФД может получить \(M'\) единиц молока в сумме содержимого двух бидонов.

ФД хочет выбрать \(a\) и \(b\) так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть \(M\) - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы \(M\) было как можно меньше. Помогите ФД определить это минимально возможное значение для \(M\).

ФД хочет выбрать \(a\) и \(b\) так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть \(M\) - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы \(M\) было как можно меньше. Помогите ФД определить это минимально возможное значение для \(M\).

Для первых пяти тестов гарантируется, что \(B\) не более 100. Во всех тестах гарантируется, что \(B\) не более 1,000,000.

Правила игры "Копыто, Бумага, Ножницы" просты. Две коровы играют друг против друга. Они обе считают до трёх, а затем одновременно делают жест, представляющий копыто, бумагу или ножницы. Копыто выигрывает у ножниц, ножницы выигрывают у бумаги, бумага выигрывает у копыта. Конечно может быть и ничья, если обе коровы сделали один и тот же жест.

Фермер Джон наблюдает как две коровы играют серию из \(N\) игр (\(1 \leq N \leq 100\)). К несчастью, ФД видя три различных жеста, не понимает, какой из них означает копыто, какой бумагу, какой ножницы.

ФД назначил жестам цифры 1 2 3. Помогите ФД определить максимально возможное количество игр, в которых выиграет первая корова, при подходящем назначении цифр жестам.

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

Помогите ФД определить минимальное количество применений машины, чтобы все коровы оказались в не опрокинутом положении.

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

\(N\) стогов сена расположены в различных целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземлилась в позицию \(x\), этот стог взрывается с радиусом взрыва 1, что означает, что стоги сена, которые находятся на расстоянии 1 от этого стога, тоже взрываются - одновременно, но уже с радиусом взрыва, равным 2. На следующем шагу взрываются все в радиусе взрыва, но новые взрывы будут уже с радиусом 3. В общем случае, в момент времени \(t\) взрывается некоторое количество коров и каждый взрыв имеет радиус \(t\). Эти взрывы инициируют взрывы коров попавших в зону поражения в момент времени \(t+1\) с радиусами взрывов \(t+1\) и т.д

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

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

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

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

Определение:

• программа это непустая последовательность операторов.
• Оператор имеет форму "PRINT \(c\)" где \(c\) - целое число, или "REP \(o\)", за которым следует программа, за которой следует "END", где \(o\) - целое число не менее 1.

• Выполнение программы исполняет операторы последовательности.
• Выполнение оператора "PRINT \(c\)" добавляет \(c\) в выходную последовательность.
• Выполнение оператора, начинающегося с "REP \(o\)" выполняет внутреннюю программу \(o\) раз

Пример программы Беси.

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

Эта программа выведет последовательность \([1,2,2,1,2,2,1,2,2]\).

Беси хочет вывести последовательность \(N\) (\(1 \le N \le 100\)) положительных целых чисел. Эльза предложила Беси использовать не более \(K\) (\(1 \le K \le 3\)) операторов "PRINT". Заметим, что Беси может использовать сколько хочет операторов "REP". Также заметим, что каждое положительное число в последовательности не более \(K\).

Для каждого \(T\) (\(1 \le T \le 100\)) независимого подтеста определите, может ли Беси написать программу, которая выведет некоторую заданную последовательность, используя не более \(K\) операторов "PRINT".

**Замечание: Время на тест в этой задаче 4 сек, в два раза больше, чем по умолчанию.**

Вам дано целое число \(N\) (\(2\le N\le 2000\)). Рассмотрим все перестановки \([p_0,p_1,\dots, p_{N-1}]\) из \([0,1,2\dots, N-1]\).

Пусть \(f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|\) означает минимальную абсолютную разность между двумя последовательными элементами в \(p\). Также обозначим \(S_N\) множество всех таких перестановок \(p\), которые достигают максимальной возможной величины \(f(p)\).

Также Вам дополнительно дано \(K\) (\(0\le K\le N\)) ограничений вида \(p_i=j\) (\(0\le i,j<N\)). Посчитайте количество перестановок в \(S_N\), удовлетворяющих всем ограничениям, по модулю \(10^9+7\).

Очень жаркое лето. Фермер Дон решил купить некоторое количество кондиционеров.

У ФД имеется \(N\) коров (\(1 \leq N \leq 20\)), которые живут в амбаре, содержащем последовательность стойл, пронумерованные \(1 \ldots 100\). Корова \(i\) занимает диапазон стойл, начиная с \(s_i\) и заканчивая в \(t_i\). Диапазоны стойл, занимаемые коровами, не пересекаются. У коров различные требования к охлаждению. Корова \(i\) должна быть охлаждена на количество \(c_i\). Это значает, что для всех стойл, занимаемых коровой \(i\) температура должна быть уменьшена на \(c_i\) единиц.

Амбар содержит \(M\) кондиционеров, помеченных \(1 \ldots M\) (\(1 \leq M \leq 10\)). \(i\)-ый кондиционер стоит \(m_i\) единиц денег, если работает и охлаждает воздух (уменьшает температуру) в стойлах начиная в \(a_i\) и заканчивая в \(b_i\). Если работает, \(i\)-ый кондиционер уменьшает температуру во всех стойлах этого диапазона на величину \(p_i\) (\(1 \leq p_i \leq 10^6\)). Диапазоны стойл кондиционеров могут перекрываться.

Определите минимальное количество денег, которое ФД должен потратить, чтобы сделать температуру комфортабельной для всех коров во всех стойлах. Гарантируется, что это возможно сделать.

Штамп-живопись это раскрашивание чёрным и белым цветом холста размером \(N \times N\) ячеек, где определённые ячейки закрашиваются, а другие - нет. Этот холст может быть представлен массивом символов \(N\times N\) (\(1\le N\le 20\)). The \(i\)-ый вход \(j\)-ой колонки массива равен символу '*', если холст содержит чернила в этой ячейке и символ '.' в противном случае.

У Беси есть план рисунка, а Фермер Джон дал ей штамп размером \(K\times K\) (\(1\le K\le N\)) который она может использовать для закраски холста размером \(N \times N\). Беси может поворачивать штамп на \(90^{\circ}\) по часовой стрелке и применять его для закраски холста в любом месте, если штамп помещается целиком на холсте. Формально, Беси выбирает такие целые числа \(i,j\), что \(i \in [1,N-K+1]\) и \(j \in [1, N-K+1]\); и затем для каждого \((i',j')\) такого, что \(1 \le i', j' \le K\), ячейка холста \((i+i'-1, j+j'-1)\) закрашивается в чёрный цвет, если в штампе было чернило в позиции \((i', j')\). Беси может поворачивать свой штамп в любой момент между закрашиваниями. Если ячейку закрасили она остаётся закрашенной навсегда.

ФД интересно может ли Беси создать свой рисунок, используя его штамп. Для каждого из \(T\) (\(1 \le T \le 100\)) подтестов помогите ФД получить ответ.

Рассмотрим 4-гранные кости

Кость A имеет числа 4, 5, 6, 7 на своих гранях.

Кость B имеет числа 2, 4, 5, 10 на своих гранях.

Кость C имеет числа 1, 4, 8, 9 на своих гранях.

Эти кости удовлетворяют довольно интересному свойству: A бьёт B, B бьёт C, C бьёт A. В частности, ни одна из этих костей не является "наилучшей", бьющёй две других. В этом случае, когда ни одна из трёх костей не является "наилучшей" и нет двух костей с олинаковой вероятностью победить, мы называем множество из таких трёх костей "не-транзитивным".

Вам дали числа на гранях двух 4-гранных костей A и B. Помогите коровам определить, есть ли способ назначить числа на гранях третьей кости С так, чтобы множество стало "не-транзитивным". Числа на всех гранях всех костей - целые в интервале от 1 до 10 включительно.

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

\(N\) коров (\(1\le N\le 10^4\)) стоят в ряд. \(i\)-ая корова слева имеет метку \(i\) для каждого \(1\le i\le N\). ФД говорит коровам повторять следующие действия до тех пор, пока коровы не вернуться к тому же порядку, с которого начинали:

• По заданной перестановке \(A\) длины \(N\), коровы изменяют их порядок так, что \(i\)-ая корова слева до изменения становится \(A_i\) коровой слева после изменения

Например, если \(A=(1,2,3,4,5)\) тогда коровы выполнят один шаг. Если \(A=(2,3,1,5,4)\), тогда коровы выполнят 6 шагов. Порядок коров слева направо после каждого из шагов будет таким:

• 0 шаг: \((1,2,3,4,5)\)
• 1 шаг: \((3,1,2,5,4)\)
• 2 шаг: \((2,3,1,4,5)\)
• 3 шаг: \((1,2,3,5,4)\)
• 4 шаг: \((3,1,2,4,5)\)
• 5 шаг: \((2,3,1,5,4)\)
• 6 шаг: \((1,2,3,4,5)\)

Определите сумму всех положительных целых чисел \(K\) таких, что существует перестановка длины \(N\), которая требует от коров выполнить ровно \(K\) шагов.

Поскольку это число может быть очень большим, выведите ответ по модулю \(M\) (\(10^8\le M\le 10^9+7\), \(M\) - простое).