Назовем целое положительное число хорошим, если в его десятичной записи нет цифры 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$$$.
1256133 17
1 2 3 3
9544715561 525
2 3 4 6
239923 5
1 1 2 2
1218633757639 976272
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$$$.
Название |
---|