Codeforces Round 792 (Div. 1 + Div. 2) |
---|
Закончено |
Главный секрет киноиндустрии заключается в том, что известный фильм «Люси» основан на реальных событиях, а в главных ролях была именно Тётя Люсине. Спойлер: в конце фильма Люси(не) превращается в компьютер. Причём компьютер необычный, в нём есть информация про все секреты вселенной, но в виде бинарной строки. Эту бинарную строку вам и нужно расшифровать самым-самым естественным образом.
Дана бинарная строка $$$s$$$. Необходимо разбить её на произвольное количество непересекающихся подстрок так, чтобы сумма двоичных чисел, образованных этими подстроками, была точной степенью двойки, либо сказать, что это невозможно. Каждый символ $$$s$$$ должен принадлежать ровно одной подстроке из разбиения.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В единственной строке каждого набора входных данных вводится бинарная строка $$$s$$$ ($$$1 \le |s| \le 10^6$$$).
Гарантируется, что сумма $$$|s|$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите ответ на задачу следующим образом:
4 00000 01101 0111011001011 000111100111110
-1 3 1 3 4 4 5 5 8 1 2 3 3 4 4 5 6 7 7 8 10 11 12 13 13 5 1 5 6 7 8 11 12 14 15 15
В первом наборе входных данных невозможно разбить строку так, чтобы получить степень двойки.
Во втором наборе входных данных возможно следующее разбиение:
Название |
---|