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

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

Вам нужно распилить деревянный брус на несколько кусков в заданных местах. Распилочная компания берет \(k\) рублей за распил одного бруска длиной \(k\) метров на две части.

Понятно, что различные способы распила приводят к различной суммарной стоимости заказа. Например, рассмотрим брус длиной 10 метров, который нужно распилить на расстоянии 2, 4 и 7 м, считая от одного конца. Это можно сделать несколькими способами. Можно распилить сначала на отметке 2 м, потом 4 и, наконец, 7 м. Это приведет к стоимости 10+8+6=24, потому что сначала длина бруса, который пилили, была 10 м, затем она стала 8 м, и, наконец, 6 м. А можно распилить иначе: сначала на отметке 4 м, затем 2, затем 7м. Это приведет к стоимости 10+4+6=20, что лучше.

Определите минимальную стоимость распила бруса на заданные части.

Триангуляцией \(N\)-угольника называется набор из \(N\)-3 непересекающихся (кроме как в вершинах многоугольника) диагоналей, разбивающих \(N\)-угольник на \(N\)-2 треугольника.

Для заданного выпуклого \(N\)-угольника найдите триангуляцию, у которой сумма длин диагоналей, входящих в триангуляцию, минимальна.

Триангуляцией \(N\)-угольника называется набор из \(N\)-3 непересекающихся (кроме как в вершинах многоугольника) диагоналей, разбивающих \(N\)-угольник на \(N\)-2 треугольника.

Для заданного выпуклого \(N\)-угольника найдите триангуляцию, у которой длина самой большой диагонали, входящей в триангуляцию, минимальна.