Крош называет положительное целое число интересным, если оно представляется в виде суммы двух различных степеней двойки, то есть $$$x$$$ $$$-$$$ интересное, если существуют два различных неотрицательных целых числа $$$i \ge 0$$$, $$$j \ge 0$$$, $$$i \neq j$$$, что $$$x = 2^i + 2^j$$$. У Кроша есть большое число $$$m$$$, записанное в двоичной системе счисления. Длина числа не превосходит $$$2*10^5$$$. Помогите Крошу посчитать, сколько есть интересных чисел среди чисел от $$$1$$$ до $$$m$$$.
В первой строке записано число $$$1 \le n \le 2 * 10^5$$$ - длина числа. В следующей строке записано число $$$m$$$ из $$$n$$$ цифр, представленное в двоичной системе счисления. Каждая цифра равна $$$0$$$ или $$$1$$$, при этом первая цифра обязательно равна $$$1$$$.
Выведите ответ на задачу - количество интересных чисел среди чисел от $$$1$$$ до $$$m$$$.
4 1010
5
2 11
1
| Krosh Kaliningrad Contest 2 |
|---|
| Закончено |
