$$$2^n$$$ команд участвуют в плей-офф турнире. Турнир состоит из $$$2^n - 1$$$ игры. Они проводятся следующим образом: на первом этапе команды делятся на пары: команда $$$1$$$ играет против команды $$$2$$$, команда $$$3$$$ играет против команды $$$4$$$ и так далее (таким образом, в этой фазе будет сыграно $$$2^{n-1}$$$ игры). Когда команда проигрывает игру, она выбывает, и каждая игра приводит к выбыванию одной команды (нет ничьих). После этого остается $$$2^{n-1}$$$ команд. Если остается только одна команда, она объявляется чемпионом; в противном начинается второй этап, где играется еще $$$2^{n-2}$$$ игр: в первой из них победитель игры «$$$1$$$ против $$$2$$$» играет против победителя игры «$$$3$$$ против $$$4$$$», затем победитель игры «$$$5$$$ против $$$6$$$» играет против победителя игры «$$$7$$$ против $$$8$$$» и так далее. Этот процесс повторяется до тех пор, пока не останется только одна команда.
Уровень навыков $$$i$$$-й команды равен $$$p_i$$$, где $$$p$$$ — перестановка чисел $$$1$$$, $$$2$$$, ..., $$$2^n$$$ (перестановка — это массив, в котором каждый элемент от $$$1$$$ до $$$2^n$$$ встречается ровно один раз).
Задана строка $$$s$$$, состоящая из $$$n$$$ символов. Эти символы обозначают результаты игр на каждом этапе турнира следующим образом:
Назовем целое число $$$x$$$ выигрышным, если существует такая перестановка $$$p$$$, что команда с уровнем навыков $$$x$$$ выиграет турнир. Найдите все выигрышные целые числа.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 18$$$).
Вторая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов 0 и/или 1.
Выведите все выигрышные целые числа $$$x$$$ в порядке их возрастания.
3 101
4 5 6 7
1 1
2
2 01
2 3
Название |
---|