В секретной лаборатории профессора Хаоса проходит эксперимент по выращиванию особо опасных бактерий. В начале первого дня эксперимента у Хаоса имеется \(a\) особо опасных бактерий.

Каждый день эксперимента устроен следующим образом. Рано утром профессор достает из контейнера все свои бактерии и помещает их в инкубатор, где бактерии начинают делиться. Вместо каждой бактерии образуется \(b\) новых бактерий.

После извлечения бактерий из инкубатора \(c\) из них используются для проведения различных опытов и затем уничтожаются. Если после извлечения из инкубатора имеется менее c бактерий, для проведения опытов используются все имеющиеся бактерии, и эксперимент заканчивается.

Оставшиеся бактерии в конце дня необходимо поместить в контейнер и продолжить использовать в эксперименте. Однако в контейнер можно поместить не более \(d\) бактерий, поэтому если число оставшихся бактерий больше \(d\), то в контейнер помещаются \(d\) бактерий, а остальные уничтожаются.

Теперь профессор Хаос хочет выяснить, сколько особо опасных бактерий будет у него в контейнере после \(k\)-го дня эксперимента. Помогите ему найти ответ на этот вопрос.

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

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

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

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

Проходя по дороге, Томас забирает округленную вверх половину лежащих на ней монет. Таким образом, если на дороге лежит \(x\) монет, то, пройдя по этой дороге, Томас заберет [\(x/2\)] монет, а на дороге останется ⌊\(x/2\)⌋ монет. По дорогам, на которых монет уже нет, перемещать Томаса не разрешается.

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

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

Внутренние регистры процессора хранят вещественные числа в виде двоичной дроби ровно с n двоичными знаками после точки. Число знаков до точки не ограничено. В таком формате представимы числа, равные \(p/2^n\) для некоторого целого \(p\). Число \(x\), полученное в результате выполнения арифметических операций над вещественными числами, при сохранении в регистр процессора заменяется на ближайшее представимое число, а если x находится ровно посередине между двумя представимыми числами, то на большее из них.

Для хранения чисел в памяти используется формат, при котором вещественное число представляется в виде двоичной дроби ровно с \(k\) двоичными знаками после точки (\(k \le n\), число знаков до точки, так же как и у регистров, не ограничено). В таком формате представимы в точности числа, равные
\(p/2^{k}\) для некоторого целого \(p\). При загрузке числа из памяти в регистр процессора число дополняется нулями до n двоичных знаков после точки. При сохранении числа y в память из регистра оно заменяется на ближайшее представимое число, а если y находится ровно посередине между двумя представимыми числами, то на большее их них.

Например, пусть \(n = 10\), \(k = 5\). Число 1 хранится в памяти в виде \(1.00000_2\), число 3 хранится в памяти как \(11.00000_2\). При загрузке в регистры числа дополняются нулями до \(1.0000000000_2\) и \(11.0000000000_2\), соответственно. Пусть было выполнено деление 1 на 3. Если результат деления \(1/3\) записать в двоичной системе, получится \(0.(01)_2\) — здесь, как и в случае десятичных дробей, часть в скобках означает период бесконечной двоичной дроби. При сохранении в регистре процессора эта дробь будет приближена значением \(0.0101010101_2\). Умножим теперь это число на 3. Получится число \(0.1111111111_2\), в таком же виде оно хранится в регистре процессора. При сохранении в память оно приближается числом \(1.00000_2\), как ближайшей двоичной дробью с 5 знаками после точки.

Петя заметил, что если загрузить в регистры единицу и целое число \(v\), поделить 1 на v, затем умножить результат деления на v и сохранить результат умножения в память, то итоговое сохраненное значение не всегда равно 1. Например, если \(v = 40\), то после деления в регистре оказывается значение \(0.0000011010_2\), после умножения на \(v\) значение \(1.0000010000_2\), после сохранения в память оно преобразуется в \(1.00001_2\). Петя называет такие числа неудачными.

Петю заинтересовал вопрос, какие целые числа от 1 до \(r\) являются неудачными. Помогите ему выяснить это

Пете подарили на день рождения новую карточную игру «Салют». Эта игра предназначена для одного человека. В комплект игры входит колода, состоящая из n карт. На каждой карте написано целое число от 1 до \(m\).

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

• Сбросить любую карту, находящуюся в руке. Сброшенная карта отправляется в снос и не может быть далее использована в игре.
• Если в колоде еще есть карты, то взять в руку верхнюю карту колоды. Такой ход можно сделать только, если в руке у игрока строго меньше, чем \(k\) карт.
• Выложить карту из руки на стол. Карту с числом \(x\) можно выложить в том случае, если игрок до этого уже выложил на стол карты с числами 1, 2, \(\dots\) , \(x−1\), но еще не выложил карту с числом \(x\).

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

Шахматный аналитик Миша занимается исследованием перемещений произвольных шахматных фигур по доскам произвольного размера. Вот несколько определений из его последней монографии.

Обобщенной шахматной доской \(m \times n\) будем называть прямоугольную доску, которая имеет \(m\) столбцов и \(n\) рядов. Клетка обобщенной доски задается парой целых чисел \((c, r)\), где \(c\) изменяется от 1 до \(m\) и задает номер столбца, а \(r\) от 1 до \(n\) и задает номер ряда.

Обобщенный конь - это вымышленная шахматная фигура, задаваемая конечным множеством возможных ходов, где каждый ход - это пара целых чисел. Если пара \((x, y)\) входит в множество возможных ходов, то своим ходом обобщенный конь может переместиться из клетки с координатами \((c, r)\) в клетку с координатами \((c + x, r + y)\), если эта клетка принадлежит доске. Например, обычный шахматный конь — это не что иное, как обобщенный конь, задаваемый множеством \({(2, 1),(1, 2),(−1, 2),(−2, 1),(−2, −1),(−1, −2),(1, −2),(2, −1)}.\)

Будем говорить, что обобщенный конь прекрасно перемещается по прямоугольной доске \(m \times n\), если из любой клетки этой доски до любой другой он может добраться, не выходя за границы доски. Например, обычный шахматный конь прекрасно перемещается по доске \(8 \times 8\).

Недавно Миша выбрал числа \(a, b, c\) и \(d\) и сформулировал гипотезу: «если обобщенный конь прекрасно перемещается по доске \(a \times b\), то он прекрасно перемещается по доске \(c \times d\)». Помогите определить, верна ли эта гипотеза для заданных \(a, b, c\) и \(d\), и если нет, то приведите пример обобщенного коня, который является для нее контрпримером.