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

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

«Оптимизированный» процесс контроля заключается в следующем:

1. Контролер выполняет $$$k$$$ взвешиваний, и нумерует их от $$$1$$$ до $$$k$$$.
2. Для $$$i$$$-го взвешивания случайно выбирается число $$$a_i$$$ — количество деталей, это число записывается в журнал взвешиваний.
3. Выбранное количество произвольно взятых деталей помещается на весы, и их суммарная масса $$$w_i$$$ также записывается в журнал.
4. По выполнению $$$k$$$ взвешиваний, журнал анализируется, и делается вывод о наличии или отсутствии брака.

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

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

Город представлен в виде квадратной клетчатой доски размера $$$N\times N$$$. Каждая клетка представляет один дом. Гремлины боятся яркого света и поэтому прячутся в темноте. Далее, по мере того как люди ложатся спать, свет в домах гаснет. Гремлины могут перемещаться по горизонтали и по вертикали от одного дома, где не горит свет, к другому. Как только они достигают дома, который находится на границе города, они сбегают из города.

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

При выполнении различных физических расчетов часто приходится иметь дело не только с числами, но и с размерностями величин. При этом размерности могут получаться весьма сложными и их требуется сокращать: например, размерность кг/(кг/м/с) это просто м/с.

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

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

Если дольки апельсина можно поровну разделить среди $$$n$$$ человек, то скажем что он подходит для такой компании. А какое минимальное количество долек $$$m$$$ должно быть в апельсине, чтобы он подходил $$$k$$$ различным компаниям (компании считаются различными, если они состоят из разного числа человек)?

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

Стало доброй традицией на соревнованиях по программированию решать задачу про Ханойскую башню.

Кратко напомним правила этой игры-головоломки.

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

Требуется переместить все диски с исходного стержня $$$A$$$ на результирующий стержень $$$B$$$, используя третий стержень $$$C$$$ как вспомогательный. За один ход разрешается взять один (обязательно верхний) диск и надеть его на другой стержень, возможно пустой. Причем, диск большего диаметра запрещается класть на диск меньшего размера. Во многих учебниках по программированию приводится процедура решения этой головоломки.

Procedure Hanoi (X, Y, Z: char; N: integer);
Begin
 If N>0 then 
    Begin
       Hanoi (X, Z, Y, N-1);
       Writeln('Disk ', N, ' from ', X, ' to ', Y);
       Hanoi (Z, Y, X, N-1)
    End
End;

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

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

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

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

На экзамене по информатике Вася решал следующую задачу:

«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу $$$a$$$ каменей или увеличить количество камней в куче в два раза. Например, если $$$a = 2$$$, имея кучу из $$$10$$$ камней, за один ход можно получить кучу из $$$12$$$ или $$$20$$$ камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

К сожалению Вася не помнит значения $$$a$$$ и $$$n$$$, которые были на экзамене, но помнит при каких начальных $$$s$$$ выигрывали Петя или Ваня. Также он помнит что $$$a$$$, $$$n$$$ и $$$s$$$ не превосходили $$$10^3$$$. Напишите программу, которая по различным значениям $$$s$$$ и информации о выигрышах для этих $$$s$$$ найдет минимальные подходящие $$$a$$$ и $$$n$$$.

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

Альтернативой может служить использование булевых уравнений. Будем говорить, что битовая последовательность x₁, x₂, x₃, …, x_n удовлетворяет некоторому уравнению

Назовем последовательность $$$a_0$$$, $$$a_1$$$, $$$a_2$$$, … $$$a_{k-1}$$$ «самоописывающейся», если значение $$$a_i$$$ — это количество чисел $$$i$$$, встречающихся в этой последовательности.

Например, такова последовательность 1, 2, 1, 0 — «0» встречается 1 раз, «1» встречается 2 раза, «2» встречается 1 раз и «3» вообще не встречается.

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

Существует множество вариантов игры в крестики и нолики. Рассмотрим одну из них.

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

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

Гарантируется, что для входных данных, существует хотя бы одно правильное решение.

У вас есть две строки, состоящие из строчных латинских букв: шаблон $$$p$$$ и текст $$$t$$$. Кроме того шаблон может содержать символ $$$+$$$, который означает повторение предшествующего ему символа один или более раз, и символ $$$*$$$, означающий повторение предшествующего ему символа любое количество раз.

Вам необходимо ответить на вопрос - соответствует ли текст $$$t$$$ шаблону $$$p$$$.

Например, текст"eboooy" соответствует шаблонам "ebo+y", "ebo*o*o+y+", но не соответствует "ebb*oy" или "ebooo".

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

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

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