Selrr

17.02.2022 05:39

Информатика

Есть ответ 👍

Очень Поликарп выписал на доске n цифр, отличных от нуля. Таким образом, на доске записана строка s длины n, состоящая из цифр от 1 до 9.
Введем понятие подстроки строки s: подстрока строки s — это последовательность, состоящая из произвольного количества символов строки s, которые идут в строке s подряд.
Теперь он хочет найти в этой строке подстроку максимальной длины, которая удовлетворяет следующим условиям:
• длина подстроки — четное число;
• пусть x — длина подстроки, тогда сумма первых x/2 цифр подстроки равна сумме
последних x/2 цифр подстроки.
Перед вами стоит задача определить максимальную длину подстроки строки s, которая
удовлетворяет описанным условиям.
Формат входных данных
В первой строке следует целое число n (2 6 n 6 5 000) — длина строки s.
Во второй строке следует строка s длины n, состоящая из цифр от 1 до 9.
Формат выходных данных
Выведите максимальную длину подстроки строки s, которая удовлетворяет описанным
условиям. Если ни одной подходящей подстроки не существует, выведите 0.
Примеры
стандартный ввод стандартный вывод
9
123856931 4

8
12345678 0

12
434892555555 12
Замечание
В первом примере ответной подстрокой является подстрока 3856 длины 4, которая начинается в позиции 3 и заканчивается в позиции 6. Сумма первой половины цифр равна
11 и сумма второй половины цифр равна 11, поэтому эта подстрока удовлетворяет всем
условиям.
Во втором примере нет ни одной подстроки, удовлетворяющей всем условиям, поэтому
нужно вывести 0.