Сколько существует клеток на доске размером \(K\)x\(K\) таких, что шахматный конь, стоящий на этой клетке, бьет ровно \(N\) полей?

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

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

Положив фигуры, Андрюша собирается выпустить хомячка на стол. Чтобы он не упал со стола, у него не должно быть возможности добраться от точки, в которую Андрюша его выпустит, до края стола. Хомячок не может перелезать через кубики, и, в частности, не может пролезть между двумя кубиками, имеющими общее ребро. Стол существенно больше каждой из фигур.

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

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

Последовательность из нулей и единиц четной длины назовем справедливой, если на четных местах этой последовательности столько же единиц, сколько на нечетных. Например, последовательность "011011" является справедливой, а последовательность "011101" – нет.

Задана некоторая последовательность нечетной длины из нулей и единиц. Из нее разрешается удалить одну цифру. Какую цифру следует удалить, чтобы последовательность стала справедливой?

Например, из последовательности "0111011" с этой целью можно удалить вторую цифру.

Если в Microsoft Excel выделить две соседние клетки с числами, а потом “потянуть” за правый нижний уголок мышью, то следующие клетки заполнятся числами, образуя арифметическую прогрессию.

Шпион Коля зашифровал и послал в центр радиограмму. Он использовал такой способ шифровки: сначала выписал все символы своего сообщения (включая знаки препинания и т.п.), стоявшие на четных местах, в том же порядке, а затем ­– все символы, стоящие на нечетных местах. Напишите программу, которая расшифровывает сообщение.