В исследовательской лаборатории фирмы Robots&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robots&Co заинтересовались вопросом, сколько существует различных программ, состоящих из K инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами (X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.

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

Петя придумал новую игру. На стол кладется кучка из N спичек, и затем Петя с Ваней по очереди берут спички из кучки. Первым берет Петя, ему разрешается взять от 1 до K спичек. Затем игрок может взять любое количество спичек, не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Например, если N = 10, K = 5, то на первом ходу Петя может взять 1, 2, 3, 4 или 5 спичек, если Петя возьмет 3, то на следующем ходу Ваня может взять 1, 2, 3 или 4, и если Ваня возьмет 1, то Петя затем может взять 1 или 2, и т. д. Проигрывает тот, кто возьмет последнюю спичку.

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

Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте h_i. Поскольку главный редактор газеты настаивает, чтобы название статьи было «Восхождение и спуск», решено было не упоминать о некоторых днях похода, рассказав лишь о 2k+1 дне, причем если статья будет рассказывать о x₁-ом, x₂-ом, …, x_2k+1-ом (x₁ < x₂ < … < x_2k+1)) дне, то должно выполняться условие h_x1 < h_x2 < … < h_xk < h_xk+1 > h_xk+2 > … > h_x2k+1 . Найдите максимальное k, для которого можно соответствующим образом выбрать 2k+1 день.