Динамическое программирование

Учительница математики попросила школьников составить арифметическое выражение так, чтобы его значение было равно данному числу N, и записать его в тетради. В выражении могут быть использованы натуральные числа, не превосходящие K, операции сложения и умножения, а также скобки. Петя очень не любит писать, и хочет придумать выражение, содержащее как можно меньше символов. Напишите программу, которая поможет ему в этом.

Входные данные
В первой строке входных данных содержатся два натуральных числа: N (1 <= N <= 10000) - значение выражения и K (1 <= K <= 10000) - наибольшее число, которое разрешается использовать в выражении.

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

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

При организации движения по сложным перекресткам, для того, чтобы траектории водителей, выполняющих различные маневры не пересекались, вводят ограничения на возможные маневры водителей, в зависимости от того, по какой полосе движения водитель подъехал к перекрестку. Для этого используется знак <<движение по полосам>>, на рисунке справа приведен пример такого знака, установленного перед одним из перекрестков в Санкт-Петербурге.

Рассмотрим дорогу, подходящую к перекрестку, на котором сходится \(m\) дорог. Водитель, подъезжающий к перекрестку по этой дороге, потенциально может продолжить свое движение в \(m\) различных направлениях — обратно по дороге, по которой он приехал, а также по одной из оставшихся \(m - 1\) дорог. Пронумеруем возможные направления числами от 1 до \(m\) слева направо с точки зрения подъезжающего водителя, номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 — поворот на самую левую из дорог, и т. д.

Пусть дорога содержит \(n\) полос для движения. Пронумеруем полосы от 1 до \(n\) слева направо, самая левая полоса получит номер 1, следующая номер 2, и т. д. Знак <<движение по полосам>> разрешает каждой из полос движение по некоторым из \(m\) возможных направлений. При этом должны выполняться следующие условия:

1. если с \(i\)-й полосы разрешено движение в \(a\)-м направлении, а с \(j\)-й полосы — в \(b\)-м направлении, причем \(i < j\), то \(a \le b\);

2. с каждой полосы разрешено движение хотя бы в одном направлении;

3. в каждом направлении разрешено движение хотя бы с одной полосы.

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

Формат входных данных
Строка содержит два целых числа: \(m\) и \(n\) (\(2 \le m \le 50\), \(1 \le n \le 15\)).

Формат выходных данных
Выведите одно число — количество возможных знаков <<движение по полосам>>, которые можно установить перед перекрестком.

В примере возможны следующие варианты знаков <<движение по полосам>>:

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



Для задания конфигурации головоломки удобно рассмотреть ее развертку - "разрезать" поверхность цилиндра вдоль вертикальной линии, проходящей по границам квадратиков, и обозначить черные клетки символом "1", а белые - символом "0". Пусть, например, одна из возможных разверток головоломки, приведенной на рисунке, следующая (на рисунке видно только первые три столбца этой развертки):
        000110 001110 101000 001000 011111 011110
Задача решающего головоломку состоит в том, чтобы, поворачивая слои, добиться того, чтобы все вертикальные столбцы были различны. Например, головоломка приведенная выше, не решена, поскольку два из ее столбцов (четвертый и пятый на приведенной развертке) одинаковы. Если же повернуть нижний слой влево на один квадратик, развертка головоломки примет следующий вид:
        000110 001110 101000 001000 011111 111100
Теперь все столбцы различны и, следовательно, головоломка решена.

Для того, чтобы решать головоломку было интереснее, на ее раскраску наложено дополнительное условие: нельзя повернуть один из слоев головоломки меньше, чем на полный оборот таким образом, что внешний вид головоломки останется тем же. Так, например, для n  = 6 слой с раскраской "010101" не разрешается, поскольку при его повороте на 2 квадратика внешний вид головоломки не меняется.

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


Входные данные
В первой строке вводится число n  - количество слоев в головоломке и количество квадратиков в одном слое (1 <= n  <= 200). Следующие n
 строк содержат по n  символов, каждый из которых равен 0 или 1 - развертку головоломки.

Выходные данные
Если решить головоломку можно, в первой строке выведите слово "Yes". В этом случае следующие n  строк должны содержать произвольную развертку решенной головоломки.

Если решить головоломку нельзя, выведите в первой и единственной строке выходных данных слово "No".

 

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

В ряд выписаны n чисел. Требуется поставить между каждой парой соседних чисел один из знаков "+" или "×" таким образом, чтобы значение получившегося выражения было как можно больше. Использовать скобки не разрешается.

Например, для последовательности чисел 1, 2, 3, 1, 2, 3 оптимально расставить знаки следующим образом: 1 + 2 × 3 × 1 × 2 × 3. Значение выражения в этом случае равно 37.

Входные данные
В первой строке вводится число n (2 <= n <= 200000). Вторая строка содержит n целых чисел - числа, между которыми следует расставить знаки. Все числа находятся в диапазоне от 0 до 10⁹.

Выходные данные
Выведите оптимальное выражение. В качестве знака "×" выводите символ "*" (звездочку). Если оптимальных решений несколько, выведите любое из них.

Сережа - большой любитель игр на сотовом телефоне. Недавно он скачал из интернета новую игру "Пузырьки 1D". Опишем правила игры.

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

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

Например, ниже на рисунке показана позиция, содержащая 10 пузырьков. В ней четыре группы, содержащие 3, 2, 4 и 1 пузырек, соответственно. Если взорвать группу, содержащую четыре пузырька, то игрок получит 16 очков, и верхние 5 пузырьков опустятся вниз. В получившейся позиции 6 пузырьков, и две группы по 3 пузырька в каждой.


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

Входные данные
На вход программы поступает одна строка, состоящая из букв "R", "G", "B и "Y", описывающая начальную позицию. Буквы задают цвета пузырьков в порядке просмотра сверху вниз ("R" означает красный пузырек, "G" – зеленый, "B" – синий, а "Y" – желтый). В заданной позиции не менее двух и не более 100 пузырьков.

Выходные данные
Выведите одно число – максимальное количество очков, которое сможет заработать Сережа. Если уничтожить все пузырьки невозможно, выведите 0.

Пояснения
В первом примере следует действовать следующим образом: сначала надо взорвать группу из четырех красных пузырьков, получив 16 очков. Затем надо взорвать в любом порядке получившиеся две группы по 3 пузырька, получив по 9 очков за каждую.

Почти все Королевство Байтленд покрыто лесами и реками. Малые реки сливаются в более крупные реки, которые, в свою очередь, сливаются друг с другом; в конечном счете, все реки сливаются вместе в одну большую реку. Большая река впадает в море вблизи города Байттаун.

В Байтленде имеется n лесозаготовительных поселков, каждый из которых расположен вблизи какой-либо реки. В настоящее время в Байттауне находится большая пилорама, которая обрабатывает все деревья, срубленные в Королевстве. Деревья сплавляются вниз по рекам от поселков, где они срублены, к пилораме в Байттауне. Король Байтленда решил поставить k дополнительных пилорам в поселках, чтобы уменьшить стоимость сплава деревьев. После установки пилорам деревья не обязательно должны сплавляться в Байттаун, а могут быть обработаны на ближайшей пилораме, находящейся ниже по течению рек. Очевидно, что деревья, срубленные в окрестности поселка с пилорамой, вообще не сплавляются по рекам.

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

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

Задание
Напишите программу, которая:
<> * читает из стандартного ввода количество поселков, количество дополнительных пилорам, которые будут установлены, количество срубленных в каждом поселке деревьев и описание рек,
*вычисляет минимальную стоимость сплава деревьев после установки дополнительных пилорам,
*выводит результат в стандартный вывод.

Входные данные
Первая строка входных данных содержит два целых числа: n — количество поселков, не считая Байттауна (2 ≤ n ≤ 100), и k
 — количество дополнительных пилорам, которые будут установлены (1 ≤ k ≤ 50 и k ≤ n). Поселки нумеруются числами 1 , 2 ,...., n , а Байттаун имеет номер 0.

Каждая из последующих n строк содержит три целых числа, разделенных одним пробелом. Строка i + 1 содержит:

w_i — количество деревьев, срубаемых в поселке i за год (0 ≤ w_i ≤ 10 000),
v_i — ближайший поселок (либо Байттаун) вниз по реке от поселка i (0 ≤ v_i ≤ n),
d_i — расстояние (в километрах) по реке от поселка i до поселка v_i (1 ≤ d_i ≤ 10 000).
Гарантируется, что суммарная стоимость сплава всех деревьев к пилораме в Байттауне не превосходит 2 000 000 000 центов в год.
В 50% тестов число n не превосходит 20.

Выходные данные
Первая и единственная строка выходных данных должна содержать одно целое число: минимальную стоимость сплава (в центах).

Пояснения


Рисунок сверху иллюстрирует входные данные примера. Номера поселков указаны внутри кругов. Числа под кругами обозначают количество деревьев, срубаемых вблизи данного поселка. Числа над стрелками указывают длины рек.

Пилорамы должны быть установлены в поселках 2 и 3.

Рассмотрим неубывающую последовательность s₁, ..., s_n + 1 ( s_i <= s_i + 1 для 1 <= i <= n ). Последовательность m₁, ..., m_n, в которой каждый член определен как m_i = ½ * ( s_i + s_i + 1 ) для 1 <= i <= n, назовем “средней последовательностью” для последовательности s₁, ... s_n + 1. Например, средняя последовательность для последовательности 1, 2, 2, 4 есть 1.5, 2, 3. Заметим, что элементы средней последовательности могут быть дробными числами. Тем не менее, в данной задаче используются только те средние последовательности, в которых все числа целые. Для заданной неубывающей последовательности из n целых чисел m1, ..., mn необходимо вычислить количество всех неубывающих последовательностей из n + 1 целых чисел s₁, ..., s_n + 1, для которых заданная последовательность m₁, ..., m_n является средней последовательностью.

Задание
Напишите программу, которая:

• читает из стандартного ввода неубывающую последовательность целых чисел;
• вычисляет количество всех неубывающих последовательностей целых чисел, для которых заданная последовательность является средней последовательностью;
• выводит ответ в стандартный вывод.

Входные данные
Первая строка стандартного ввода содержит одно целое число n (2 <= n <= 5000000). Оставшиеся n строк содержат значения последовательности m₁, ..., m_n. Строка i + 1 содержит одно целое число mi (0 <= mi <= 1000000000).

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

У Пети есть набор из N кирпичиков. Каждый кирпичик полностью окрашен в один из K цветов, i-й кирпичик имеет размер 1×1×Li. Петя знает, что он может построить из всех кирпичиков прямоугольную стену толщиной 1 и высотой K, причем первый горизонтальный слой кирпичиков в стене будет первого цвета, второй - второго и т. д. Теперь Петя хочет узнать, может ли он из своего набора построить две прямоугольные стены, обладающие тем же свойством. Помогите ему выяснить это.

Входные данные
В первой строке входных данных задаются числа N и K (1 <= N <= 5000, 1 <= K <= 100). Следующие N строк содержат описание Петиных кирпичиков: сначала длина L_i, затем номер цвета C_i (1 <= L_i <= 100, 1 <= C_i <= K). Известно, что у Пети не более 50 кирпичиков каждого цвета.

Выходные данные
Выведите в первой строке YES, если Петя сможет построить из всех своих кирпичиков две прямоугольные стены высоты K, j-й слой кирпичиков в каждой из которых будет j-го цвета, и NO в противном случае. В случае положительного ответа, выведите во второй строке в произвольном порядке номера кирпичиков, из которых следует построить первую стену (кирпичики нумеруются в том порядке, в котором они заданы во входных данных, начиная с 1). Если решений несколько, можно выдать любое из них.

В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат - ловушку для космического мусора. Для того, чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (N), на юг (S), на запад (W), на восток (E), вверх (U) и вниз (D). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {N, S, W, E, U, D}.

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

Пусть, например, заданы следующие правила:

Направление	Правило
N	N
S	NUSDDUSE
W	UEWWD
E
U	U
D	WED

Тогда при выполнении команды S(3) мусорщик выполнит следующие действия:
1) переместится на 1 метр в направлении S
2) выполнит последовательно команды N(2), U(2), S(2), D(2), D(2), U(2), S(2), E(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:

SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEEПо заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.

Входные данные
Первые шесть строк входных данных задают правила для команд с направлением N, S, W, E, U и D соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {N, S, W, E, U, D}, затем пробел и параметр команды - целое положительное число, не превышающее 100.

Выходные данные
Выведите единственное число - количество перемещений, которое совершит ловушка. Гарантируется, что ответ не превышает 10⁹.

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

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

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

Например, для пяти городов, соединенных дорогами так, как это показано на рисунке 1, три наиболее удаленных друг от друга города - это города 1, 2 и 5 (взаимная удаленность равна 2 + 3 + 3 = 8), а для городов на рисунке 2 - это любые три города, выбранные из множества {1, 2, 4, 5} (удаленность 2 + 2 + 2 = 6).

Входные данные
В первой строке вводится число N - количество городов (3 <= N <= 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит K_i - количество городов, с которыми он соединен дорогами (1 <= K_i < N), а затем K_i чисел - номера городов, с которыми он соединен. Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.

Выходные данные
Выведите три различных числа - номера трех наиболее удаленных друг от друга городов в произвольном порядке. Если решений несколько, выведите любое из них

Играют двое. Задаётся какая-то дата 2020 года. Каждый игрок на своём ходе называет более позднюю дату, увеличивая на 1 или 2 либо день в месяце, либо месяц, но не то и другое сразу. При этом сочетание дня и месяца должно оставаться датой. Игрок, назвавший 31 декабря, проигрывает. Оба играют наилучшим образом. Исходя из заданной даты вывести, кто выиграет.

Входные данные
В первой строке находятся числа, обозначающие день и месяц.

Выходные данные
Вывести 1, если выигрывает первый (начинающий) игрок, или 2 - в противном случае.

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



В основании (нижнем ряду) такой лесенки расположено N
 кубиков, а каждый следующий ряд кубиков укладывается на предыдущий так, что один кубик укладывается ровно на один нижестоящий кубик, а по крайней мере на самый правый и самый левый кубики предыдущего ряда новые кубики не кладутся (чтобы получилась ступенька).

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

Входные данные
Вводятся два числа N и K (1≤N≤100, 1≤K≤100).

Выходные данные
Выведите одно число – количество различных лесенок. Гарантируется, что правильный ответ не будет превышать 10¹⁸.

Поле для детской игры представляет собой последовательность кружков, первый из которых является стартом, а последний – финишем. На некоторых из кружков указано действие, которое нужно совершить фишке, попавшей на этот кружок: передвинуть фишку на несколько кружков вперед или назад, или сделать еще один ход. Изначально фишки всех K игроков ставятся на старт. Затем они по очереди делают ходы, которые заключаются в следующем. Игрок получает очередное "случайное" число, используя генератор псевдослучайных чисел, описанный ниже, и передвигает свою фишку на столько кружков вперед, какое число он получил (если это число больше количества кружков до финиша, то игрок останавливается на финише). Если на кружке, куда он попал в результате своего хода, написано, что требуется совершить некоторое действие, то игрок совершает это действие. После этого он совершает действие, указанное на кружке, куда он попал в результате предыдущего действия и т. д. до тех пор, пока он не попадет на кружок, на котором не указано никакого действия.

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

Генератор псевдослучайных чисел устроен следующим образом. Его параметрами являются натуральные числа a, b, c и x0. Генератор порождает последовательность натуральных чисел x₁, x₂, x₃, … по следующему правилу: xn+1 равно остатку от деления (ax_n+ b) на c (при n = 0, 1, 2, …). Для игры используются числа x₁, x₂, x₃, … именно в этом порядке (число x0 не используется). Все игроки используют общий датчик, то есть, если, например, первый игрок использовал число x1 и передал ход второму, то тот будет использовать число x₂, а если ему потребуется повторить ход, то x₃ и т. д.

Входные данные
В первой строке входных данных содержатся числа a, b, c, x0, описывающие генератор псевдослучайных чисел. Все числа целые неотрицательные и не превосходят 1000; c > 0. В следующей строке записаны числа K – количество игроков и L – количество кружков поля, включая старт и финиш (1 ≤ K, L ≤ 1000). В следующих L–2 строках записаны команды во втором, третьем, …, L–1-м кружке (в кружках старта и финиша никаких команд нет и при попадании туда ничего делать не нужно). Каждая команда записывается парой чисел.

Если первое число равно единице, то это означает, что нужно сделать дополнительный ход. При этом, если второе число равно T и T > 0, то нужно сделать ход на T кружков вперед, если T < 0 – то на |T| кружков назад, а если T = 0, то нужно снова воспользоваться датчиком псевдослучайных чисел и сделать указанное им количество шагов вперед.

Если первое число равно нулю, то ничего делать не нужно. (Если первое число равно нулю, то второе число также равно нулю.)

Другие значения первое число принимать не может.

Число T целое, и всегда таково, что при соответствующем ходе фишка не окажется за пределами доски (но может оказаться на клетке Старт или Финиш). Если же T = 0 и очередное "случайное" число больше, чем количество кружков до финиша, то фишка останавливается на финише.

Выходные данные
Выведите одно число – номер игрока-победителя. Гарантируется, что одна из фишек обязательно достигнет финиша, причем за время игры будет совершено не более миллиона перемещений (на "случайное" число или число, указанное в кружке).

Новый учитель математики ввел в школе оригинальную систему оценки учеников – рейтинговую. На каждом уроке школьнику предлагалось выполнить задание, состоящее из нескольких задач. После этого учитель увеличивал рейтинг школьника на число, равное отношению количества решенных им сегодня задач к количеству задач, решенных им на прошлом занятии. Например, если сегодня ученик решил 5 задач, а вчера – две, то к его рейтингу сегодня прибавится = 2.5. Изначально рейтинг равен нулю; он начинает увеличиваться со второго дня. Если в один из дней какой-то ученик не решал ни одной задачи, то учитель объявлял его полной бездарностью и переводил в другой класс (с облегченным изучением математики), поэтому каждый день все ученики старались решить хотя бы одну задачу.

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

Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 1 000) – количество уроков, которые провел в школе учитель до того, как его уволили.

В следующей строке содержатся числа a₁, a₂, …, a_N– количество задач, которые учитель предложил школьникам на первом, втором, …, N-м уроках соответственно (1 ≤ a_i ≤ 100).

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

Во второй строке выведите N чисел – количество задач, которые должен решить школьник в каждый из дней. Если вариантов несколько, выведите один любой из них.

Слово называется палиндромом, если его первая буква совпадает с последней, вторая – с предпоследней и т.д. Например: "abba", "madam", "x".

Для заданного числа K слово называется почти палиндромом, если в нем можно изменить не более K любых букв так, чтобы получился палиндром. Например, при K = 2 слова "reactor", "kolobok", "madam" являются почти палиндромами (подчеркнуты буквы, заменой которых можно получить палиндром).

Подсловом данного слова являются все слова, получающиеся путем вычеркивания из данного нескольких (возможно, одной или нуля) первых букв и нескольких последних. Например, подсловами слова "cat" являются слова "c", "a", "t", "ca", "at" и само слово "cat" (а "ct" подсловом слова "cat" не является).

Требуется для данного числа K определить, сколько подслов данного слова S являются почти палиндромами.

Входные данные
В первой строке вводятся два натуральных числа:N (1 ≤ N ≤ 5 000) – длина слова и K (0 ≤ K ≤ N).

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

Выходные данные
Требуется вывести одно число – количество подслов слова S, являющихся почти палиндромами (для данного K).

Сверхсекретный завод, расположенный высоко в горах, занимается изготовлением новейших систем контроля торсионных полей – нанокристаллов. Нанокристалл состоит из нескольких атомов, некоторые из которых попарно связаны сверхпрочными торсионными связями.

Нанокристалл стабилен, если между любыми двумя его атомами можно построить соединяющую их цепочку связей, возможно с использованием других атомов. Например, из четырех атомов A, B, C и D, в котором между собой связаны пары A - B, A - C, B - C и B - D, стабилен. Если же, например, в нанокристалле из данных четырех атомов связаны только пары A - B и C - D, то кристалл нестабилен, поскольку, например, A и C не соединены никакой цепочкой связей.

Для любой пары атомов стабильного нанокристалла определена их взаимная удаленность – минимальная длина цепочки из связей, которая их соединяет. Например, рассмотрим описанный выше нанокристалл. Взаимная удаленность атомов A и B равна единице (они соединены напрямую), а взаимная удаленность C и D равна двум (они соединены цепочками C - B - D и C - A - B - D, длина кратчайшей цепочки равна двум).

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

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

Входные данные
На вход программы поступает число c (1<c<10 000).

Выходные данные
В первой строке  выведите два целых числа n и m – количество атомов и связей в разработанном нанокристалле, соответственно. Будем считать, что атомы нанокристалла пронумерованы от 1 до n. Следующие m строк должны содержать по два целых числа – пары атомов, которые следует соединить торсионными связями. Если решений несколько, выведите любое.

Если искомого нанокристалла не существует, выведите в первой и единственной строке  выходных данных два нуля.

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

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

Если вершина \(Y\) — ребенок вершины \(X\), то говорят, что вершина \(X\) является родителем вершины \(Y\). У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.

Соединим каждую вершину кроме корня с ее родителем. Заметим, что для каждой вершины существует ровно один путь, ведущий в нее от корня.

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

1. если вершина красная, то ее родитель — черный;

2. количество черных вершин на пути от корня до любой вершины, у которой отсутствует хотя бы один ребенок, одно и то же.

Примеры двоичного дерева, вершины которого раскрашены в два цвета, приведены на следующем рисунке.

Если считать закрашенные вершины черными, а незакрашенные — красными, то дерево на рисунке (а) является красно-черным деревом, а деревья на рисунках (б) и (в) — нет. Для дерева на рисунке (б) нарушается первое свойство — у красной вершины 5 родитель 2 также красный, а в дереве на рисунке (в) нарушается второе свойство — на пути от корня до вершины 1 одна черная вершина, а, например, на пути от корня до вершины 3 — две.

Для заданного двоичного дерева подсчитайте число способов раскрасить его вершины в черный и красный цвет так, чтобы оно стало красно-черным деревом.

Формат входных данных
Первая строка содержит число \(n\) — количество вершин в дереве (\(1 \le n \le 1000\)).

Пусть вершины дерева пронумерованы числами от \(1\) до \(n\). Следующие \(n\) строк содержат по два числа — для каждой вершины заданы номера ее левого и правого ребенка. Если один из детей отсутствует, то вместо его номера записан ноль. Гарантируется, что входные данные корректны, то есть набор чисел действительно задает двоичное дерево.

Формат выходных данных
Выведите одно число — количество способов раскрасить вершины заданного во входном файле двоичного дерева в красный и черный цвета так, чтобы оно стало красно-черным деревом.

Все допустимые способы раскрасить вершины дерева из первого примера приведены на следующем рисунке.

Сегодня Игорь получил долгожданное разрешение на проведение эксперимента по изучению протекания химических реакций в магнитном поле. При этом используются две установки — генератор магнитного поля и манипулятор, соединяющий реагенты.

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

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

Формат входных данных
На первой строке записано целое число \(n\) — количество этапов эксперимента (\(1 \le n \le 100\)).

Следующие \(n\) строк содержат описание этапов. Пронумеруем этапы от 1 до \(n\) в некотором произвольном порядке. Тогда \(i\)-я из этих строк описывает \(i\)-й этап. Каждый этап описывается последовательностью целых чисел. Первое число равно нулю, если на этом этапе Игорь управляет генератором, и единице, если он управляет манипулятором. Затем записано целое число \(r_i\) — количество этапов, которые должны быть выполнены перед выполнением данного. За ним следуют номера этих этапов — \(r_i\) различных целых чисел в диапазоне от 1 до \(i - 1\).

Формат выходных данных
На первой строке выведите минимальное количество перемещений, которые придется совершить Игорю. На второй строке выведите перестановку чисел от 1 до \(n\) — последовательность, в которой следует выполнять этапы. Если решений несколько, выведите любое.

Сегодня на страницах газеты <<Математический досуг>> была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из \(m\) строк и \(n\) столбцов. В каждой ячейке таблицы записано некоторое целое число.

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

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

Напишите программу, которая по заданной таблице найдет искомый прямоугольник.

Формат входных данных
На первой строке записаны два целых числа \(m\) и \(n\) (\(2 \le m, n \le 300\)). Далее следует описание таблицы — \(m\) строк, каждая из которых содержит по \(n\) целых чисел \(a_{i,j}\) (\(-10^4 \le a_{i,j} \le 10^4\)).

Формат выходных данных
На первой строке выведите целое число \(s\) — максимальную сумму чисел на границе искомого прямоугольника. На второй строке выведите четыре натуральных числа: \(x_1, y_1, x_2, y_2\) — координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь \(x\) — номер строки, а \(y\) — номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

Вася очень хочет попасть на сборы в СУНЦ и, к счастью, живет недалеко от него. Поэтому он решил дойти до места проведения сборов пешком. Васе известен план города - какие перекрестки соединены улицами и сколько времени требуется, чтобы пройти по каждой улице. Движение по любой улице разрешено в обе стороны.

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

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

Дом Васи находится около перекрестка с номером 1, а СУНЦ - около перекрестка с номером N. Таким образом, перемещение Васи от дома до СУНЦа выглядит следующим образом. В начале глава выбирает дороги, на которых будет проводиться уборка, затем Вася выбирает улицу, по которой он пойдет от перекрестка 1 (Вася достаточно наблюдателен, чтобы заметить, на каких улицах идет уборка). Когда он доходит до конца выбранной улицы и оказывается на перекрестке, процесс повторяется: глава вновь выбирает улицы для уборки, и машины туда мгновенно перемещаются, а затем Вася - улицу, по которой идти, и т. д. Процесс продолжается, пока Вася не попадет в СУНЦ.

Ваша задача - выяснить, за какое минимально возможное время Васе удастся достичь СУНЦа при условии, что глава администрации всегда действует оптимально.

Входные данные
Первая строка содержит числа N - количество перекрестков в городе, M - количество улиц и K - количество снегоуборочных машин (1 <= N <= 100, 0 <= K <= M <= 20000). Следующие M строк содержат описания улиц в следующем формате: a и b - номера перекрестков, которые данная улица соединяет, t - время движения по данной улице (целое положительное число, не превосходящее 1000).

Выходные данные
Выведите одно число - минимальное время, за которое Вася может добраться до СУНЦа. или -1, если добраться туда невозможно.