Монокарп работает директором в школе и для подарков своим школьникам на Новый год он приготовил $$$n$$$ конфет. В школе Монокарпа учатся $$$a$$$ мальчиков и $$$b$$$ девочек.
Монокарп решил, что подарит каждому мальчику одинаковое положительное количество конфет и подарит каждой девочке одинаковое положительное количество конфет, при этом количество конфет, которые он подарит каждому мальчику должно быть строго меньше, чем количество конфет, которые он подарит каждой девочке.
Монокарп хочет подарить как можно больше из своих $$$n$$$ конфет. Перед вами стоит задача определить минимальное количество конфет, которые останутся у Монокарпа после раздачи конфет, если вы можете выбрать количество конфет, которые получит каждый мальчик, и выбрать количество конфет, которые получит каждая девочка.
Считайте, что входные данные таковы, что каждый мальчик гарантировано может получить по одной конфете, а каждая девочка может получить по две конфеты, то есть $$$a + 2 \cdot b \le n$$$.
В первой строке следуют три целых числа $$$n$$$, $$$a$$$ и $$$b$$$ ($$$3 \le n \le 1\,000$$$, $$$1 \le a, b \le 100$$$, $$$a + b \cdot 2 \le n$$$) — количество конфет у Монокарпа, количество мальчиков и количество девочек.
Выведите минимальное количество конфет, которые могут остаться у Монокарпа после раздачи конфет, если вы можете выбрать сколько конфет получит каждый мальчик и сколько конфет получит каждая девочка.
34 5 6
0
42 4 7
2
В первом примере Монокарп может подарить каждому мальчику по $$$2$$$ конфеты, а каждой девочке по $$$4$$$ конфеты. Тогда он сможет подарить все имеющиеся у него конфеты.
Во втором примере Монокарп может подарить каждому мальчику по $$$3$$$ конфеты, а каждой девочке по $$$4$$$ конфеты. Тогда он сможет подарить $$$3 \cdot 4 + 4 \cdot 7 = 40$$$ конфет, и у него останется всего $$$2$$$ конфеты.
Монокарп играет в компьютерную игру. Сейчас он хочет пройти первый уровень этой игры.
Уровень — это прямоугольное клеточное поле из $$$2$$$ строк и $$$n$$$ столбцов. Персонаж Монокарпа изначально стоит в клетке $$$(1, 1)$$$ — на пересечении строки $$$1$$$ и столбца $$$1$$$.
Персонаж Монокарпа за одно действие может переместиться из одной клетки в другую, если они — соседние по стороне и/или углу. Формально, из клетки $$$(x_1, y_1)$$$ можно за одно действие переместиться в клетку $$$(x_2, y_2)$$$, если $$$|x_1 - x_2| \le 1$$$ и $$$|y_1 - y_2| \le 1$$$. Очевидно, выходить за границы уровня нельзя.
На некоторых клетках находятся ловушки. Если персонаж Монокарпа оказывается в такой клетке, он умирает, и игра заканчивается.
Чтобы пройти уровень, персонаж Монокарпа должен оказаться в клетке $$$(2, n)$$$ — на пересечении строки $$$2$$$ и столбца $$$n$$$.
Помогите Монокарпу определить, можно ли пройти уровень.
В первой строке задано одно целое число $$$n$$$ ($$$3 \le n \le 100$$$) — количество столбцов.
Далее следуют две строки, описывающие уровень. $$$i$$$-я из этих строк описывает $$$i$$$-ю строку уровня — строка состоит из символов '0' и '1'. Символ '0' соответствует безопасной клетке, символ '1' — клетке с ловушкой.
Дополнительное ограничение на входные данные: клетки $$$(1, 1)$$$ и $$$(2, n)$$$ — безопасные.
Выведите YES, если уровень можно пройти, и NO, если нельзя.
3 000 000
YES
4 0011 1100
YES
4 0111 1110
NO
6 010101 101010
YES
Возможный путь в первом примере: $$$(1, 1) \rightarrow (2, 2) \rightarrow (2, 3)$$$.
Возможный путь во втором примере: $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (2, 4)$$$.
Возможный путь в четвертом примере: $$$(1, 1) \rightarrow (2, 2) \rightarrow (1, 3) \rightarrow (2, 4) \rightarrow (1, 5) \rightarrow (2, 6)$$$.
На первое собрание кружка по программированию Берляндского ГУ пришли $$$n$$$ студентов ($$$n$$$ — четно). Было решено поделить всех студентов на две группы. У каждой группы будет ровно по одному занятию в неделю в один из будних дней (понедельник, вторник, среда, четверг или пятница), причем дни занятий у каждой группы должны быть разными. Также было решено, что количество студентов в каждой группе должно быть одинаковым.
Каждый из студентов заполнил форму, в которой отметил дни недели, в которые ему было бы удобно посещать занятия.
Перед вами стоит задача определить, возможно ли выбрать два различных будних дня в неделю, в которые будут проходить занятия у каждой из групп, а также поделить всех студентов на две группы таким образом, чтобы каждый из студентов занимался в один из тех дней, в который ему удобно, при этом количество студентов в каждой из групп должно быть одинаковым.
В первой строке следует четное целое число $$$n$$$ ($$$2 \le n \le 1\,000$$$) — количество студентов.
В $$$i$$$-й из следующих $$$n$$$ строк следует $$$5$$$ целых чисел $$$0$$$ или $$$1$$$, причем $$$j$$$-е число равно $$$1$$$, если $$$i$$$-му студенту удобно ходить на занятия в $$$j$$$-й будний день, или $$$j$$$-е число равно $$$0$$$, если $$$i$$$-му студенту неудобно ходить на занятия в $$$j$$$-й будний день.
Гарантируется, что каждый из студентов хочет ходить на занятия хотя бы в один из будних дней.
Если возможно разделить всех студентов на две равные группы и выбрать дни для занятий так, чтобы всем студентам было удобно, выведите «YES» (без кавычек). В противном случае, выведите «NO» (без кавычек).
4 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0
YES
2 0 0 0 1 0 0 0 0 1 0
NO
В первом примере возможно распределить студентов так, чтобы удовлетворить всем описанным условиям. Для этого в одну группу нужно распределить первого и третьего студентов, которые будут заниматься в четверг, то есть в четвертый будний день, а в другую группу — второго и четвертого студентов, которые будут заниматься во вторник, то есть во второй будний день.
Во втором примере невозможно разделить студентов на группы так, чтобы группы занимались в разные будние дни.
В данной задаче вам предстоит восстановить информацию о прямоугольнике. Известно, что сумма каких-то двух сторон прямоугольника равна $$$x$$$, а сумма каких-то трех сторон прямоугольника равна $$$y$$$. Обратите внимание, что каждая из четырех сторон прямоугольника может быть учтена в каждой из сумм не более одного раза.
Перед вами стоит задача определить минимально возможный периметр прямоугольника, сумма каких-то двух сторон которого равна $$$x$$$, а сумма каких-то трех сторон равна $$$y$$$. Обратите внимание, что длины стороны ответного прямоугольника не обязательно являются целыми числами, но они строго положительны.
В первой строке следуют два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le 10^{9}$$$) — сумма каких-то двух и сумма каких-то трех сторон прямоугольника.
Если не существует ни одного подходящего прямоугольника, выведите $$$-1$$$.
В противном случае, выведите одно вещественное число — минимально возможный периметр подходящего прямоугольника. Абсолютная или относительная погрешность ответа не должна превышать $$$10^{-4}$$$.
10 15
20.0000
6 4
7.0000
10 2
-1
7 4
7.5000
500000000 1000000000
1250000000.0
В первом примере все стороны ответного прямоугольника одинаковы и равны $$$5$$$.
Во втором примере две стороны ответного прямоугольника равны $$$3$$$, а другие две стороны равны $$$0.5$$$.
В третьем примере не существует ни одного подходящего прямоугольника.
В четвертом примере две стороны ответного прямоугольника равны $$$3.5$$$, а другие две стороны равны $$$0.25$$$.
У Монокарпа есть массив целых чисел $$$a$$$, состоящий из $$$n$$$ элементов. Обозначим среднее арифметическое всех элементов массива за $$$k$$$ (обратите внимание, что $$$k$$$ может быть вещественным числом).
Среднее арифметическое массива из $$$n$$$ элементов — это сумма всех элементов массива деленная на $$$n$$$, то есть на количество элементов массива.
Монокарп решил удалить из массива $$$a$$$ ровно два элемента, при этом он хочет, чтобы после удаления среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива по-прежнему было равно $$$k$$$.
Перед вами стоит задача определить количество пар позиций $$$[i, j]$$$ ($$$i \lt j$$$) таких, что если удалить элементы из этих позиций, среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива будет равно $$$k$$$, то есть будет равно среднему арифметическому $$$n$$$ элементов изначального массива $$$a$$$.
В первой строке следует целое число $$$n$$$ ($$$3 \le n \le 200\,000$$$) — количество элементов в массиве Монокарпа.
Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно $$$i$$$-му элементу массива Монокарпа.
Выведите количество пар позиций $$$[i, j]$$$ ($$$i \lt j$$$) таких, что если удалить элементы из этих позиций, среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива будет равно $$$k$$$, то есть будет равно среднему арифметическому $$$n$$$ элементов изначального массива $$$a$$$.
4 8 8 8 8
6
3 50 20 10
0
5 1 4 7 3 5
2
В первом примере можно удалить любую пару чисел, так как все элементы массива одинаковы.
Во второй примере нельзя удалить ни одной пары чисел таким образом, чтобы среднее арифметическое не изменилось.
В третьем примере можно удалить пару элементов в позициях $$$1$$$ и $$$3$$$ или пару элементов в позициях $$$4$$$ и $$$5$$$.
Монокарп попал на необитаемый остров. Он решил обойти весь остров и обнаружил, что на нем есть $$$n$$$ пальм, причем на $$$i$$$-й пальме растет $$$a_i$$$ кокосов.
Монокарп решил выбрать целое положительное число $$$x$$$ и собрать все кокосы со всех пальм, количество кокосов на которых является целой положительной степенью числа $$$x$$$. Иными словами, Монокарп соберет все кокосы с $$$i$$$-й пальмы, если число $$$a_i$$$ можно представить в виде числа $$$x^{m}$$$, где $$$m$$$ — целое положительное число.
Перед вами стоит задача помочь Монокарпу и определить максимально возможное количество кокосов, которое он может собрать, выбрав какое-то число $$$x$$$.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество пальм с кокосами.
Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно количеству кокосов, которые растут на $$$i$$$-й пальме.
Выведите максимальное количество кокосов, которые может собрать Монокарп, выбрав какое-то целое положительное число $$$x$$$.
5 4 8 25 5 16
30
3 9 27 40
40
6 1 1 4 1 1 1
5
В первом примере Монокарпу нужно выбрать $$$x = 5$$$. Тогда он сможет собрать кокосы с третьей и четвертой пальм, и суммарное количество собранных кокосов будет равно $$$25 + 5 = 30$$$.
Во втором примере Монокарпу нужно выбрать $$$x = 40$$$. Тогда он сможет собрать кокосы с третьей пальмы, то есть количество собранных кокосов будет равно $$$40$$$. Если бы Монокарп выбрал число $$$3$$$, то смог бы собрать кокосы с первой и второй пальм. Количество кокосов на этих пальмах равно $$$9 + 27 = 36$$$, но это количество меньше, что для $$$x = 40$$$.
В третьем примере Монокарпу нужно выбрать $$$x = 1$$$. Тогда он сможет собрать $$$5$$$ кокосов со всех пальм, кроме третьей.
Монокарп тренер команд Берляндского ГУ по программированию. Он решил собрать тренировку для своих команд перед квалификационным этапом.
У Монокарпа есть $$$n$$$ задач, которые еще не решал ни один из его студентов. У $$$i$$$-й задачи есть тема $$$a_i$$$ (целое число от $$$1$$$ до $$$200\,000$$$) и сложность $$$b_i$$$ (целое число от $$$1$$$ до $$$200\,000$$$), причем все задачи попарно различны, то есть нет двух задач, у которых одинаковы и тема, и сложность.
Монокарп решил выбрать из $$$n$$$ задач ровно $$$3$$$ задачи для тренировки, при этом должно выполняться хотя бы одно из двух условий (возможно, оба):
- темы всех трех выбранных задач различны;
- сложности всех трех выбранных задач различны.
Перед вами стоит задача определить количество способов, которыми Монокарп может выбрать три задачи для тренировки.
В первой строке следует целое число $$$n$$$ ($$$3 \le n \le 200\,000$$$) — количество задач, которые есть у Монокарпа.
В $$$i$$$-й из следующих $$$n$$$ строк следуют по два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le 200\,000$$$) — тема и сложность $$$i$$$-й задачи.
Гарантируется, что нет двух задач, у которых одинаковы и тема, и сложность.
Выведите количество способов выбрать три задачи для тренировки, которые удовлетворяют описанным в условии требованиям.
4 2 4 3 4 2 1 1 5
3
5 1 5 2 4 3 3 4 2 5 1
10
В первом примере можно взять следующие наборы по три задачи:
- задачи с номерами $$$1$$$, $$$2$$$, $$$4$$$;
- задачи с номерами $$$1$$$, $$$3$$$, $$$4$$$;
- задачи с номерами $$$2$$$, $$$3$$$, $$$4$$$.
Таким образом, количество способов равно трем.
У Монокарпа есть набор из цветных шариков. Известно, что в этом наборе есть $$$a$$$ шариков красного цвета, $$$b$$$ шариков зеленого цвета и $$$c$$$ шариков синего цвета.
Монокарп может производить с шариками следующие операции. Он может взять два любых разноцветных шарика и объединить их в один, при этом два шарика, которые он взял, исчезнут, но появится новый шарик, цвет которого будет отличен от цветов обоих взятых шариков. Например, Монокарп может взять красный и синий шарики и объединить их в один шарик, цвет которого будет зеленым.
Монокарп хочет, чтобы у него стало поровну шариков каждого цвета. Перед вами стоит задача определить минимальное количество описанных операций, которые Монокарп должен произвести со своими шариками, чтобы шариков каждого цвета у него стало поровну, либо сообщить, что это невозможно.
В первой строке следуют три целых числа $$$a$$$, $$$b$$$ и $$$c$$$ ($$$0 \le a, b, c \le 10^{9}; a + b + c \gt 0$$$) — количество шариков красного, зеленого и синего цвета, которые есть у Монокарпа.
Если Монокарп не сможет сделать так, чтобы у него стало поровну шариков каждого цвета, выведите $$$-1$$$.
В противном случае, выведите минимальное количество описанных в условии операций, которые Монокарп должен произвести со своими шариками, чтобы шариков каждого цвета стало поровну.
3 3 1
1
101 101 101
0
15 30 20
-1
12 74 58
39
В первом примере нужно выполнить одну операцию — взять один красный шарик и один зеленый шарик и объединить их в один синий шарик. После этого шариков каждого цвета станет по два.
Во втором примере не нужно производить никаких операций, потому что у Монокарпа изначально одинаковое количество шариков каждого цвета.
В третьем примере невозможно сделать так, чтобы шариков каждого цвета стало поровну.
У Монокарпа есть дерево, состоящее из $$$n$$$ вершин, $$$n$$$ — четно. Дерево — это связный граф, не содержащий циклов.
Монокарп решил покрасить ровно половину вершин своего дерева в черный цвет, а другую половину вершин — в белый. При этом он хочет, чтобы после покраски вершин в дереве существовало ровно одно ребро, которое соединяет белую и черную вершины.
Перед вами стоит задача определить существует ли подходящая раскраска, и, если она существует, сообщить о любой подходящей раскраске вершин дерева.
В первой строке следует целое четное число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество вершин в дереве.
В каждой из следующих $$$n - 1$$$ строк следуют по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$) — описание ребер дерева. Гарантируется, что заданные ребра образуют дерево.
Если не существует ни одной подходящей раскраски дерева, выведите «NO» (без кавычек).
В противном случае, в первую строку выведите «YES» (без кавычек). Во вторую строку выведите $$$n$$$ целых чисел $$$0$$$ или $$$1$$$, причем $$$i$$$-е число равно $$$0$$$, если $$$i$$$-ю вершину нужно покрасить в белый цвет, и $$$i$$$-е число равно $$$1$$$, если $$$i$$$-ю вершину нужно покрасить в черный цвет. Если подходящих ответов несколько, выведите любой.
6 1 2 2 3 4 2 4 6 5 4
YES 0 0 0 1 1 1
4 3 1 3 2 3 4
NO
В первом примере можно покрасить вершины $$$1$$$, $$$2$$$ и $$$3$$$ в белый цвет, а вершины $$$4$$$, $$$5$$$ и $$$6$$$. Тогда будет ровно одно ребро, которое соединяет разноцветные вершины, это ребро между вершинами $$$2$$$ и $$$4$$$.
Во втором примере не существует ни одной подходящей раскраски.
У Монокарпа есть строка $$$s$$$, состоящая из строчных букв латинского алфавита.
Монокарп любит неубывающие строки. Строка является неубывающей, если для любой пары позиций $$$[i, j]$$$, где $$$i \lt j$$$, верно, что буква, стоящая в позиции $$$i$$$ находится в алфавите не позже, чем буква, стоящая в позиции $$$j$$$. Например, строки «aaa», «bcdef», «aappszz» являются неубывающими, а строки «ba», «abcba», «zzzzzx» — не являются.
Монокарп хочет сделать свою строку $$$s$$$ неубывающей. Для этого он может изменять буквы в любых в позициях своей строки на любые другие. Определите минимальное количество букв в строке $$$s$$$, которые надо изменить, чтобы сделать строку $$$s$$$ неубывающей, а также определите как будет выглядеть строка $$$s$$$ после этих изменений.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — длина строки $$$s$$$.
Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.
В первую строку выведите целое число $$$x$$$ — минимальное количество букв, которые нужно изменить в строке $$$s$$$, для того, чтобы она стала неубывающей.
Во вторую строку выведите неубывающую строку, которая получилась из строки $$$s$$$ после $$$x$$$ изменений. Если ответов несколько, разрешается вывести любой из них.
5 efahi
1 efghi
10 aaaabceehh
0 aaaabceehh
8 fgdadvfd
5 dddddddd
Дана матрица, состоящая из $$$n$$$ строк и $$$m$$$ столбцов.
Ячейки данной матрицы могут быть свободными или заблокированными.
Назовем путь в матрице лестницей, если он:
- начинается и заканчивается в свободной ячейке;
- посещает только свободные ячейки;
- имеет одну из двух возможных структур:
- вторая ячейка лежит на $$$1$$$ справа от первой, третья — на $$$1$$$ снизу от второй, четвертая — на $$$1$$$ справа от третьей, и так далее;
- вторая ячейка лежит на $$$1$$$ снизу от первой, третья — на $$$1$$$ справа от второй, четвертая — на $$$1$$$ снизу от третьей, и так далее.
В частности, путь, состоящий из одной ячейки, считается лестницей.
Некоторые примеры лестниц:
Изначально все ячейки в матрице свободные.
Требуется обработать $$$q$$$ запросов, каждый из которых переключает состояние одной ячейки. То есть, если клетка в данный момент свободна, то делает ее заблокированной, а если заблокирована, то делает ее свободной.
После каждого запроса требуется вывести количество различных лестниц. Две лестницы считаются различными, если существует такая ячейка, которая входит в один путь и не входит в другой.
В первой строке записаны три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1 \le n, m \le 1000$$$; $$$1 \le q \le 10^4$$$) — размерности матрицы и количество запросов.
В каждой из следующих $$$q$$$ строк записаны два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x \le n$$$; $$$1 \le y \le m$$$) — описание очередного запроса.
Выведите $$$q$$$ целых чисел — $$$i$$$-е число должно быть равно количеству различных лестниц в матрице после $$$i$$$ запросов. Две лестницы считаются различными, если существует такая ячейка, которая входит в один путь и не входит в другой.
2 2 8 1 1 1 1 1 1 2 2 1 1 1 2 2 1 1 1
5 10 5 2 5 3 1 0
3 4 10 1 4 1 2 2 3 1 2 2 3 3 2 1 3 3 4 1 3 3 1
49 35 24 29 49 39 31 23 29 27
1000 1000 2 239 634 239 634
1332632508 1333333000
Правильная скобочная последовательность (или, коротко, ПСП) — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:
- скобочные последовательности «()()» и «(())» — правильные (из них можно получить выражения «(1)+(1)» и «((1+1)+1)»);
- скобочные последовательности «)(», «(» и «)» — неправильные.
Обозначим конкатенацию двух строк $$$x$$$ и $$$y$$$ как $$$x+y$$$. Например, «()()» $$$+$$$ «)(» $$$=$$$ «()())(».
У вас есть $$$n$$$ скобочных последовательностей $$$s_1, s_2, \dots, s_n$$$. Вы можете переставить эти строки в любом порядке (можно переставлять только сами строки, но не символы в них).
Ваша задача — переставить строки в таком порядке, чтобы у строки $$$s_1 + s_2 + \dots + s_n$$$ было как можно больше непустых префиксов, являющихся ПСП.
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 20$$$).
Далее следуют $$$n$$$ строк, $$$i$$$-я из которых содержит $$$s_i$$$ — скобочную последовательность (строку, состоящую из символов «(» и/или «)». Все последовательности $$$s_i$$$ непустые, их суммарная длина не превосходит $$$4 \cdot 10^5$$$.
Выведите одно число — максимальное количество непустых префиксов, являющихся ПСП, у строки $$$s_1 + s_2 + \dots + s_n$$$, если вы переставите строки $$$s_1, s_2, \dots, s_n$$$ оптимальным образом.
2 ( )
1
4 ()()()) ( ( )
4
1 (())
1
1 )(()
0
В первом примере из условия можно склеить строки следующим образом: «(» $$$+$$$ «)» $$$=$$$ «()», у полученной строки будет один префикс, являющийся ПСП: «()».
Во втором примере из условия можно склеить строки следующим образом: «(» $$$+$$$ «)» $$$+$$$ «()()())» $$$+$$$ «(» $$$=$$$ «()()()())(», у полученной строки будет четыре префикса, являющихся ПСП: «()», «()()», «()()()», «()()()()».
В третьем и в четвертом примере всего по одной строке, поэтому поменять порядок строк невозможно.
Назовем целое положительное число хорошим, если в его десятичной записи нет цифры 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 \lt 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$$$.