← 返回题目列表

Codeforces · 1598/G

G. 好数字的总和

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

如果一个正整数的十进制表示中没有数字 0,我们就称其为“好”。

对于一个由 $$$a$$$ 组成的好数字数组,我们发现某些两个相邻元素的总和等于 $$$x$$$(即 $$$x = a_i + a_{i + 1}$$$ 对于某些 $$$i$$$)。 $$$x$$$ 也被证明是一个不错的数字。

然后数组$$$a$$$的元素被逐个写出,不带分隔符,变成一个字符串$$$s$$$。例如,如果 $$$a = [12, 5, 6, 133]$$$,则 $$$s = 1256133$$$。

给你一个字符串 $$$s$$$ 和一个数字 $$$x$$$。您的任务是确定字符串中与数组中总和为 $$$x$$$ 的相邻元素相对应的位置。如果有多个可能的答案,您可以打印其中任何一个。

输入

第一行包含字符串 $$$s$$$ ($$$2 \le |s| \le 5 \cdot 10^5$$$)。

第二行包含一个整数 $$$x$$$ ($$$2 \le x < 10^{200000}$$$)。

对输入的附加约束:答案始终存在,即您始终可以选择字符串 $$$s$$$ 的两个相邻子字符串,这样如果将这些子字符串转换为整数,它们的总和等于 $$$x$$$。

输出

在第一行中,打印两个整数 $$$l_1$$$、$$$r_1$$$,表示和的第一项 ($$$a_i$$$) 位于字符串 $$$s$$$ 中,从位置 $$$l_1$$$ 到位置 $$$r_1$$$。

在第二行中,打印两个整数 $$$l_2$$$、$$$r_2$$$,表示和的第二项 ($$$a_{i + 1}$$$) 位于字符串 $$$s$$$ 中,从位置 $$$l_2$$$ 到位置 $$$r_2$$$。

示例

输入 #1

1256133
17

输出 #1

1 2
3 3

输入 #2

9544715561
525

输出 #2

2 3
4 6

输入 #3

239923
5

输出 #3

1 1
2 2

输入#4

1218633757639
976272

输出#4

2 7
8 13

注意

在第一个示例中,$$$s[1;2] = 12$$$ 且 $$$s[3;3] = 5$$$,$$$12+5=17$$$。

在第二个示例中,$$$s[2;3] = 54$$$ 且 $$$s[4;6] = 471$$$,$$$54+471=525$$$。

在第三个示例中,$$$s[1;1] = 2$$$ 且 $$$s[2;2] = 3$$$,$$$2+3=5$$$。

在第四个示例中,$$$s[2;7] = 218633$$$ 和 $$$s[8;13] = 757639$$$、$$$218633+757639=976272$$$。