У вас есть последовательность \(a_1, a_2, \ldots, a_n\) длины \(n\), состоящая из \(0\) и \(1\). Также у вас есть последовательность \(b\), изначально пустая.
Вы выполните \(n\) операций, каждая из которых увеличивает длину последовательности \(b\) на \(1\).
- На \(i\)-й операции вы выбираете целое число \(p\) от \(0\) до \(i-1\). Вы вставляете \(0\) в \(b\) на позицию \(p+1\) (после \(p\) первых элементов), после чего инвертируете \(p\) первых элементов \(b\).
- Более формально: пусть перед \(i\)-й (\(1 \le i \le n\)) операцией последовательность \(b\) равна \(b_1, b_2, \ldots, b_{i-1}\). На \(i\)-й операции вы выбираете целое число \(p\) от \(0\) до \(i-1\) и заменяете \(b\) на \(\overline{b_1}, \overline{b_2}, \ldots, \overline{b_{p}}, 0, b_{p+1}, b_{p+2}, \ldots, b_{i-1}\). Здесь \(\overline{x}\) обозначает двоичную инверсию. Таким образом, \(\overline{0} = 1\) и \(\overline{1} = 0\).
Примеры применения операций приведены в примечании.
Определите, существует ли последовательность операций, после применения которой \(b\) будет равна \(a\). Если такая последовательность операций существует, найдите её.
Примечание
В первом наборе входных данных,
- Перед первой операцией, \(b = [\,]\). Вы выбираете \(p = 0\), после чего заменяете \(b\) на \([\, \underline{0} \,]\)
- На второй операции вы выбираете \(p = 0\) и заменяете \(b\) на \([\, \underline{0}, 0 \,]\).
- На третьей операции вы выбираете \(p = 2\) и заменяете \(b\) на \([\, 1, 1, \underline{0} \,]\).
- На четвёртой операции вы выбираете \(p = 1\) и заменяете \(b\) на \([\, 0, \underline{0}, 1, 0 \,]\).
- На пятой операции вы выбираете \(p = 3\) и заменяете \(b\) на \([\, 1, 1, 0, \underline{0}, 0 \,]\).
Таким образом, последовательность \(b\) изменяется следующим образом: \([\,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0} \,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0}, 0 \,]\) \(\xrightarrow{p \, = \, 2}\) \([\, 1, 1, \underline{0} \,]\) \(\xrightarrow{p \, = \, 1}\) \([\, 0, \underline{0}, 1, 0 \,]\) \(\xrightarrow{p \, = \, 3}\) \([\, 1, 1, 0, \underline{0}, 0 \,]\). Итоговая последовательность \(b\) равна последовательности \(a\), поэтому такой способ сделать операции является одним из корректных ответов.
Во втором наборе входных данных \(n = 1\) и единственная последовательность \(b\), которую вы можете получить, это \([\, 0 \, ]\).
В третьем наборе входных данных существует всего 6 последовательностей операций. Вот они:
- \([\,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0} \,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0}, 0 \,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0}, 0, 0 \,]\).
- \([\,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0} \,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0}, 0 \,]\) \(\xrightarrow{p \, = \, 1}\) \([\, 1, \underline{0}, 0 \,]\).
- \([\,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0} \,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0}, 0 \,]\) \(\xrightarrow{p \, = \, 2}\) \([\, 1, 1, \underline{0} \,]\).
- \([\,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0} \,]\) \(\xrightarrow{p \, = \, 1}\) \([\, 1, \underline{0} \,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0}, 1, 0 \,]\).
- \([\,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0} \,]\) \(\xrightarrow{p \, = \, 1}\) \([\, 1, \underline{0} \,]\) \(\xrightarrow{p \, = \, 1}\) \([\, 0, \underline{0}, 0 \,]\).
- \([\,]\) \(\xrightarrow{p \, = \, 0}\) \([\, \underline{0} \,]\) \(\xrightarrow{p \, = \, 1}\) \([\, 1, \underline{0} \,]\) \(\xrightarrow{p \, = \, 2}\) \([\, 0, 1, \underline{0} \,]\).
Ни одна из них не делает последовательность \(b\) равной \([\, 0, 1, 1 \,]\), поэтому ответ — «NO».