Пете подарили на день рождения новую карточную игру «Салют». Эта игра предназначена для одного человека. В комплект игры входит колода, состоящая из 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\), и если нет, то приведите пример обобщенного коня, который является для нее контрпримером.

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

В многих заданиях требуется перевести число из одной системы счисления в другую. Соня с легкостью справляется с такими заданиями, но недавно в одном из вариантов ей попалась задача, которая показалась довольно интересной: число \(x\), заданное в десятичной системе счисления, требуется перевести в (−2)-ичную систему счисления.

Формально, записью числа в (−2)-ичной системе счисления называется набор чисел \(a_0, a_1, \dots , a_{n−1}\), каждое из которых равно 0 или 1, причем \(n\) = 1 или \(a_{n−1} \ne 0\) и выполнено равенство:

\(\)x = \sum\limits_{i=0}^{n-1} a_i\cdot (-2)^i\(\)

Например, 3 в (−2)-ичной системе счисления представляется набором (1, 1, 1): действительно, \(1 · (−2)^0 + 1 · (−2)^1 + 1 · (−2)^2 = 1 − 2 + 4 = 3\).

В задаче предлагается перевести в (−2)-ичную систему счисления только одно число, но Соне стало интересно решение этой задачи в общем случае.

После долгих раздумий она обратилась к вам за помощью. Помогите ей перевести заданное число в (−2)-ичную систему счисления.

После ряда утечек конфиденциальной информации общественность всерьез задумалась о том, какие пароли следует использовать. Например, пароль «11111» — простой и его не следует использовать. Но как определить, хороший ли пароль?

Фондом Стандартизации Бизнес-процессов было проведено исследование, показавшее, что хороший пароль должен быть достаточно длинным и содержать символы разных видов. Исследование показало, что в хорошем пароле должно быть ровно n символов. Пароль должен состоять из заглавных и строчных букв латинского алфавита и цифр и удовлетворять следующим требованиям:

• в пароле должно быть хотя бы \(a\) заглавных букв;
• в пароле должно быть хотя бы \(b\) строчных букв;
• в пароле должно быть хотя бы \(c\) цифр;
• в пароле не должно быть двух одинаковых идущих подряд символов.

Помогите Фонду, напишите программу, которая по заданным параметрам генерирует подходящий пароль.

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

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

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

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

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