Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, …, a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3 = a_2 + a_4, …, a_{n-1} = a_{n-2} + a_n\). Например, последовательность \([1, 2, 1, –1]\) является гармоничной, поскольку \(2 = 1 + 1\), и \(1 = 2 + (–1)\).

Рассмотрим последовательности равной длины: \(A = [a_1, a_2, …, a_n]\) и \(B = [b_1, b_2, …, b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A, B) = |a_1 – b_1| + |a_2 – b_2| + … + |a_n – b_n|\). Например, \(d([1, 2 ,1, –1], [1, 2, 0, 0]) = |1 – 1| + |2 – 2| + |1 – 0| + |–1 – 0| = 0 + 0 + 1 + 1 = 2.\)

В конце лекции профессор написал на доске последовательность из \(n\) целых чисел \(B = [b_1, b_2, …, b_n]\) и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A = [a_1, a_2, …, a_n]\), такую, что \(d\)(\(A\), \(B\)) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A, B)\).

Требуется написать программу, которая по заданной последовательности \(B\) определяет, на каком минимальном расстоянии от последовательности \(B\) найдется гармоничная последовательность \(A\).

Коля Герасимов очень любит кефир, и в своём 1984 году он освоил все тонкости покупки этого чудесного напитка. Но однажды, как вам, наверное, известно, он попал в далёкий 2084 год, где покупка кефира представляет собой более сложный процесс.

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

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

Давным-давно в далёкой-далёкой галактике противоборствовали две огромные IT-корпорации: Pineapple и Gogol. Противостояние длится уже многие годы, но близится переломный момент: компания Gogol разработала абсолютно новое устройство, не имеющее аналогов~--- планшет Lastus 3000.

В этом устройстве используется впервые созданный искусственный интеллект (ИИ). Члены компании Pineapple пытались всеми силами отложить выход нового девайса. В конце концов, за неделю до выхода Lastus 3000 на рынок юристы обнаружили, что название искусственного интеллекта очень похоже на название телефона, который выпустила компания Pineapple 200 лет назад. Так как компания Pinapple обладает авторским правом на это название, она потребовала изменить имя искусственного интеллекта.

Pineapple утверждает, что название их телефона присутствует в качестве подстроки в имени ИИ. Название этой технологии уже было выгравировано на всех планшетах, поэтому директор Gogol предложил вместо некоторых букв в названии ИИ поставить символ "#". Так как это довольно затратно, надо найти минимальное количество символов, которые нужно заменить на "#", чтобы имя ИИ больше не содержало название телефона Pineapple в качестве подстроки. Помогите компании Gogol решить эту задачу.

Подстрокой называется непустая последовательность подряд идущих символов строки.

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

Алиса как раз из таких коллекционеров. Сейчас она очень хочет заполучить \(k\)-специальную табличку. Напомним, что табличка \(n \times n\) называется \(k\)-специальной, если выполнены следующие три условия:

* каждое число от \(1\) до \(n^2\) встречается в ней ровно \(1\) раз;

* в каждой строке числа идут в возрастающем порядке;

* сумма чисел, расположенных в \(k\)-м столбце, максимальна.

Помогите Алисе! Отыщите хотя бы одну \(k\)-специальную табличку размера \(n \times n\). Строки и столбцы нумеруются от \(1\) до \(n\), при этом строки нумеруются сверху вниз, а столбцы слева направо.

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

Рассмотрим операцию переворота целого положительного числа: при её применении десятичные цифры числа записываются в обратном порядке, затем если у результата есть ведущие нули, они отбрасываются. Например, при перевороте из числа \(123\) получается число \(321\), из числа \(130\)— число \(31\), а из числа \(31\) — число \(13\).

Оксана Филипповна загадала целое положительное число \(a\) без ведущих нулей и применила к нему операцию переворота, получилось число \(a_r\). После этого она сложила \(a\) и \(a_r\), дала Вите их сумму \(n\) и попросила его найти исходное число \(a\).

Поскольку в предложенном учительницей примере числа \(a\) и \(a_r\) были небольшими, Витя быстро угадал правильный ответ и задумался над построением общего алгоритма для решения задачи. Его интересует, как по заданному числу \(n\) найти какое-либо \(a\) или определить, что такого \(a\) не существует. Помогите Вите разработать такой алгоритм.