You are given a string $$$s$$$ consisting of $$$n$$$ characters. Each character of $$$s$$$ is either 0 or 1.
A substring of $$$s$$$ is a contiguous subsequence of its characters.
You have to choose two substrings of $$$s$$$ (possibly intersecting, possibly the same, possibly non-intersecting — just any two substrings). After choosing them, you calculate the value of the chosen pair of substrings as follows:
Calculate the maximum possible value you can get, and print it in binary representation without leading zeroes.
The first line contains one integer $$$n$$$ — the number of characters in $$$s$$$.
The second line contains $$$s$$$ itself, consisting of exactly $$$n$$$ characters 0 and/or 1.
All non-example tests in this problem are generated randomly: every character of $$$s$$$ is chosen independently of other characters; for each character, the probability of it being 1 is exactly $$$\frac{1}{2}$$$.
This problem has exactly $$$40$$$ tests. Tests from $$$1$$$ to $$$3$$$ are the examples; tests from $$$4$$$ to $$$40$$$ are generated randomly. In tests from $$$4$$$ to $$$10$$$, $$$n = 5$$$; in tests from $$$11$$$ to $$$20$$$, $$$n = 1000$$$; in tests from $$$21$$$ to $$$40$$$, $$$n = 10^6$$$.
Hacks are forbidden in this problem.
Print the maximum possible value you can get in binary representation without leading zeroes.
5 11010
11111
7 1110010
1111110
4 0000
0
In the first example, you can choose the substrings 11010 and 101. $$$f(s_1) = 26$$$, $$$f(s_2) = 5$$$, their bitwise OR is $$$31$$$, and the binary representation of $$$31$$$ is 11111.
In the second example, you can choose the substrings 1110010 and 11100.
Name |
---|