Дана строка $$$s$$$ из $$$n$$$ символов. Каждый символ $$$s$$$ — либо 0, либо 1.
Подстрока строки $$$s$$$ — это непрерывная подпоследовательность ее символов.
Вы должны выбрать две подстроки $$$s$$$ (возможно, пересекающиеся, возможно, одну и ту же два раза, возможно, непересекающиеся — две любые подстроки). После того как вы выбрали подстроки, вы считаете их стоимость следующим образом:
Посчитайте максимальную стоимость, которую вы можете получить, и выведите ее в двоичной системе счисления без ведущих нулей.
В первой строке задано число $$$n$$$ — количество символов в $$$s$$$.
Во второй строке задана $$$s$$$, состоящая из ровно $$$n$$$ символов 0 и/или 1.
Все тесты в этой задаче, кроме примеров из условия, сгенерированы случайным образом: каждый символ $$$s$$$ выбирается независимо от остальных, и для каждого символа вероятность быть 1 равна $$$\frac{1}{2}$$$.
В этой задаче ровно $$$40$$$ тестов. Тесты с $$$1$$$ по $$$3$$$ — примеры из условия; тесты с $$$4$$$ по $$$40$$$ сгенерированы случайным образом. В тестах с $$$4$$$ по $$$10$$$ $$$n = 5$$$; в тестах с $$$11$$$ по $$$20$$$ $$$n = 1000$$$; в тестах с $$$21$$$ по $$$40$$$ $$$n = 10^6$$$.
В этой задаче запрещены взломы.
Выведите максимальную стоимость, которую можно получить, в двоичной системе счисления без ведущих нулей.
5 11010
11111
7 1110010
1111110
4 0000
0
В первом примере можно выбрать подстроки 11010 и 101. $$$f(s_1) = 26$$$, $$$f(s_2) = 5$$$, их побитовое ИЛИ равно $$$31$$$, а двоичное представление $$$31$$$ — это 11111.
Во втором примере можно выбрать подстроки 1110010 и 11100.
Название |
---|