← 返回题目列表

Codeforces · 1698/G

G. 长二进制字符串

中文机器翻译题面 查看原题

有一个长度为$$$10^{100}$$$的二进制字符串$$$t$$$,最初它的所有位都是$$$\texttt{0}$$$。给定一个二进制字符串 $$$s$$$,并执行以下操作几次:

- 选择$$$t$$$的某些子字符串,并将其替换为与$$$s$$$的异或。$$$^\dagger$$$

找到满足这些约束的按字典顺序最大的$$$^\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$$$ 有一个位 $$$\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

输出 #1

1 2

输入 #2

001

输出 #2

3 4

输入 #3

1111

输出 #3

1 5

输入#4

00000

输出#4

-1

输入 #5

00000111110000011111000001111101010

输出 #5

6 37452687

注意

在第一次测试中,您可以执行以下操作。 $$$$$$\texttt{00000}\ldots \至 \color{red}{\texttt{1}}\texttt{0000}\ldots \至 \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots$$$$$$

在第二次测试中,您可以执行以下操作。 $$$$$$\texttt{00000}\ldots \至 \color{red}{\texttt{001}}\texttt{00}\ldots \至 \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots$$$$$$

在第三次测试中,您可以执行以下操作。 $$$$$$\texttt{00000}\ldots \至 \color{red}{\texttt{1111}}\texttt{0}\ldots \至 \texttt{1}\color{red}{\texttt{0001}}\ldots$$$$$$

可以证明这些字符串$$$t$$$是字典序上最大的字符串。

在第四个测试中,你无法做出任何一个位$$$\texttt{1}$$$,所以这是不可能的。