Codeforces Round 803 (Div. 2) |
---|
Закончено |
У вас есть бинарная строка $$$t$$$ длины $$$10^{100}$$$, и изначально все биты в строке равны $$$\texttt{0}$$$. Вам также дана бинарная строка $$$s$$$, и вы можете выполнять следующую операцию:
Найдите лексикографически максимальную $$$^\ddagger$$$ строку $$$t$$$, которая может получиться при выполнении этого условия, или определите, что таких строк получиться не может.
$$$^\dagger$$$ Формально, выберите индекс $$$i$$$ такой, что $$$0 \leq i \leq 10^{100}-|s|$$$. Для всех $$$1 \leq j \leq |s|$$$, если $$$s_j = \texttt{1}$$$, измените значение $$$t_{i+j}$$$. То есть если $$$t_{i+j}=\texttt{0}$$$, положите $$$t_{i+j}=\texttt{1}$$$. Иначе, если $$$t_{i+j}=\texttt{1}$$$, положите $$$t_{i+j}=\texttt{0}$$$.
$$$^\ddagger$$$ Бинарная строка $$$a$$$ лексикографически больше бинарной строки $$$b$$$ такой же длины, если в первой позиции, где $$$a$$$ и $$$b$$$ различаются, строка $$$a$$$ содержит $$$\texttt{1}$$$, а строка $$$b$$$ — $$$\texttt{0}$$$.
Единственная строка содержит бинарную строку $$$s$$$ ($$$1 \leq |s| \leq 35$$$).
Если нельзя получить подходящую под условие строку $$$t$$$, выведите -1. Иначе выведите два целых числа $$$p$$$ и $$$q$$$ ($$$1 \leq p < q \leq 10^{100}$$$) такие, что в лексикографически максимальной $$$t$$$ $$$p$$$-й и $$$q$$$-й биты равны $$$\texttt{1}$$$.
1
1 2
001
3 4
1111
1 5
00000
-1
00000111110000011111000001111101010
6 37452687
В первом примере можно выполнить следующие операции. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{1}}\texttt{0000}\ldots \to \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots$$$$$$
Во втором примере можно выполнить следующие операции. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{001}}\texttt{00}\ldots \to \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots$$$$$$
В третьем примере можно выполнить следующие операции. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{1111}}\texttt{0}\ldots \to \texttt{1}\color{red}{\texttt{0001}}\ldots$$$$$$
Можно показать, что показанные выше строки $$$t$$$ лексикографически максимальны.
В четвертом примере нельзя сделать ни один бит равным $$$\texttt{1}$$$, поэтому задача невыполнима.
Название |
---|