На занятии Егору показали последовательность из $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$ и дали задание нарисовать на доске таблицу $$$n \times n$$$: в ячейке, находящейся на пересечении $$$i$$$-й строки и $$$j$$$-го столбца, требовалось написать произведение $$$a_i \cdot a_j$$$. Егор успешно справился с этим заданием и пошел на перерыв. Вернувшись, он обнаружил, что кто-то стёр исходную последовательность, а также числа на диагонали получившейся таблицы. Помогите Егору восстановить исходную последовательность $$$a_1, a_2, \ldots, a_n$$$.
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$3 \leqslant n \leqslant 1000$$$) — длину последовательности $$$a$$$.
Каждая из следующих $$$n$$$ строк содержит $$$n$$$ целых чисел. В $$$i$$$-й строке $$$j$$$-е число содержит целое число $$$B_{i, j}$$$ ($$$1 \leqslant B_{i, j} \leqslant 10^9$$$, если $$$i \neq j$$$) — элемент таблицы Егора на пересечении $$$i$$$-й строки и $$$j$$$-го столбца. Числа на диагонали таблицы равны 0, то есть $$$B_{i,i}=0$$$.
В единственной строке выходных данных выведите $$$n$$$ натуральных чисел через пробел — исходную последовательность $$$a_1, a_2, \ldots, a_n$$$. Гарантируется, что такая последовательность существует. Если ответов несколько, выведите любой.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Обратите внимание, что подзадачи 1 и 2 не требуют прохождения теста из условия.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи | Комментарий |
| $$$0$$$ | $$$0$$$ | — | — | Тесты из условия |
| $$$1$$$ | $$$10$$$ | $$$n \leqslant 10, B_{i,j} \leqslant 2$$$ | — | — |
| $$$2$$$ | $$$10$$$ | $$$n \leqslant 10, a_i \leqslant 3$$$ | $$$1$$$ | — |
| $$$3$$$ | $$$40$$$ | $$$n \leqslant 100, B_{i,j} \leqslant 10000$$$ | $$$0, 2$$$ | — |
| $$$4$$$ | $$$40$$$ | $$$n \leqslant 1000, B_{i,j} \leqslant 10^9$$$ | $$$3$$$ | — |
40 2 3 42 0 6 83 6 0 124 8 12 0
1 2 3 4
На олимпиаде по лингвистике Оле в одном из заданий попался текст на неизвестном ей языке. Внимательно изучив текст, Оля пришла к выводу, что в этом языке слова бывают двух типов: короткие и длинные. Все короткие слова состоят из $$$a$$$ букв, а все длинные слова состоят из $$$b$$$ букв ($$$a \lt b$$$). Подсчитав слова, Оля определила, что в тексте содержится $$$n$$$ различных коротких слов и $$$m$$$ различных длинных слов. У Оли хорошо получается решать задания с неизвестными языками, так что она может определить значение любого короткого слова за $$$c$$$ секунд и может определить значение любого длинного слова за $$$d$$$ секунд.
Задание олимпиады заключается в том, чтобы написать стихотворение на загадочном языке, используя в нём слова из текста. Поскольку Оля — девочка творческая, она может составить стихотворение из любого набора слов, значения которых она понимает. Оля хочет, чтобы в её стихотворении суммарно было хотя бы $$$k$$$ букв, никакое слово не встречалось более одного раза и два слова одинаковой длины не шли подряд, иначе её стихотворение выйдет слишком скучным.
Посчитайте минимальное время, за которое Оля может определить значения необходимых ей для написания стихотворения слов.
В первой строке вводятся два натуральных числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^{18}, 1 \le m \le 10^{18} $$$) — количество различных коротких и длинных слов в тексте, данном в задании, соответственно.
Во второй строке вводится два натуральных числа $$$a$$$ и $$$b$$$ ($$$1 \le a \lt b \le 10^{18} $$$) — длина короткого и длинного слова соответственно.
В третьей строке вводятся два натуральных числа $$$c$$$ и $$$d$$$ ($$$1 \le c \le 10^6, 1 \le d \le 10^6 $$$) — время в секундах, которое потребуется Оле для определения значений одного короткого и одного длинного слова соответственно.
В четвёртой строке вводится натуральное число $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — минимальное суммарное количество букв, которое должно содержать Олино стихотворение.
Если у Оли не получится составить стихотворение, соответствующее условиям, выведите $$$-1$$$. Иначе выведите минимальное время в секундах, которое ей понадобится на определение значений слов на таинственном языке для написания стихотворения.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Обратите внимание, что подзадачи 1, 2 и 3 не требуют прохождения тестов из условия.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи | Комментарий |
| 0 | 0 | – | – | Тесты из условия |
| 1 | 10 | $$$n = m = k$$$ и $$$c \geq d$$$ | – | – |
| 2 | 10 | $$$n \leq m$$$ и $$$c \geq d$$$ | 1 | – |
| 3 | 20 | $$$n = m = k$$$ | 1 | – |
| 4 | 20 | $$$k \leq 10^4$$$ | 0 | – |
| 5 | 40 | – | 0, 1, 2, 3, 4 | – |
4 23 510 118
32
4 33 510 118
23
4 23 510 120
-1
4 23 51 1018
23
2 23 51 1013
21
Обратите внимание, что числа во входных данных и ответ могут быть больше, чем максимальное возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.
Обозначим короткое слово за «К», а длинное слово — за «Д».
В первом примере Оле выгоднее всего определить значения трёх коротких слов и двух длинных слов. Это займёт у Оли суммарно $$$3 \cdot 10 + 2 \cdot 1 = 32 $$$ секунды. В этом случае Олино стихотворение будет иметь следующий формат: КДКДК
Во втором примере Оле выгоднее всего определить значения двух коротких слов и трёх длинных слов. Это займёт у Оли суммарно $$$2 \cdot 10 + 3 \cdot 1 = 23 $$$ секунды. В этом случае Олино стихотворение будет иметь следующий формат: ДКДКД
В третьем примере Оля не может составить стихотворение, соответствующее всем ограничениям.
Даня и Андрей вместе решают головоломку. У них есть строка $$$s$$$, состоящая из строчных латинских букв и знаков вопроса («?»), а также строка $$$t$$$, состоящая только из строчных латинских букв.
Первый ход делает Даня: вместо каждого знака вопроса «?» в строке $$$s$$$ он должен вставить ровно одну строчную латинскую букву (знаки вопроса на разных позициях можно заменять как одинаковыми, так различными буквами). После этого Андрей может перемешать буквы строки $$$s$$$ в любом порядке. Даня и Андрей решат головоломку, если после их ходов будет достигнуто максимально возможное число непересекающихся вхождений строки $$$t$$$ в преобразованную строку $$$s$$$. Помогите Дане сделать первый ход.
Замените все знаки вопроса в строке $$$s$$$ так, чтобы после перемешивания букв оптимальным образом максимизировать число непересекающихся вхождений строки $$$t$$$ в полученную строку $$$s$$$.
Первая строка содержит строку $$$s$$$ из строчных латинских букв и, возможно, знаков вопроса ($$$1 \leqslant |s| \leqslant 10^6$$$).
Вторая строка содержит строку $$$t$$$ из строчных латинских букв ($$$1 \leqslant |t| \leqslant 10^6$$$).
Выведите строку $$$s$$$ после оптимального хода Дани, то есть после замены знаков вопроса на строчные латинские буквы. Если ответов, приводящих к максимальному количеству непересекающихся вхождений $$$t$$$ в $$$s$$$ несколько, выведите любой из них.
В этой задаче потестовая оценка — каждый пройденный тест оценивается в 2 балла. Чтобы ваше решение было принято на тестирование, необходимо, чтобы оно проходило тесты из условия.
?aa?ab
baab
?a?b?c?cc
aacbccc
Если изначально $$$s = ?aa?$$$, $$$t = ab$$$, то Даня может совершить такой ход: $$$s = baab$$$. Тогда Андрей может перемешать буквы следующим образом: $$$s = abab$$$. Такая строка содержит $$$2$$$ непересекающихся вхождения строки $$$ab$$$. Так как длина $$$|s|=2, |t|=4$$$, то больше двух вхождений получить невозможно.
Петя решил попробовать себя в роли инженера. Недавно он придумал очень сложный механизм. Настолько сложный, что ему самому не удалось в нём разобраться. Поэтому он обратился к Вам за помощью.
Устройство состоит из $$$n$$$ отрезков на числовой прямой. Отрезки заданы координатами начала и конца, причем эти координаты целые. Гарантируется, что длины всех отрезков положительные. Помимо этого известно, что все отрезки изначально имеют одинаковую длину.
Далее, устройство может производить следующие операции-запросы с этими отрезками:
1. Выбрать отрезок с номером $$$i$$$ и сдвинуть его влево или вправо на $$$d$$$. Например, если сдвинуть отрезок $$$[3; 7]$$$ на $$$4$$$ вправо, то получится $$$[7; 11]$$$.
2. Выбрать отрезки с номерами с $$$i$$$-го по $$$j$$$-й и расширить их все влево или вправо ровно в два раза. То есть фиксируется левый или правый конец, а противоположный сдвигается так, что длина отрезка увеличивается в два раза. Например, если отрезки $$$[3;5]$$$ и $$$[8; 12]$$$ расширить влево, то получатся отрезки $$$[1; 5]$$$ и $$$[4; 12]$$$, а если вправо — $$$[3; 7]$$$ и $$$[8; 16]$$$.
3. Выбрать отрезок с номером $$$i$$$ и вывести любой отрезок из имеющихся, содержащий $$$i$$$-й. Координата начала искомого отрезка должна быть строго меньше координаты начала $$$i$$$-го, а координата конца строго больше координаты конца $$$i$$$-го. Петю не интересует номер найденного отрезка, он хочет знать только координаты начала и конца. Например, отрезок $$$[6; 8]$$$ содержится в отрезке $$$[5; 10]$$$, но отрезки $$$[5; 9]$$$ и $$$[8; 10]$$$ не содержатся в отрезке $$$[5; 10]$$$.
Согласно Петиным расчётам, гарантируется, что координаты начала и конца любого из отрезков в течение всех операций являются положительными и не превосходят $$$10^9$$$.
Помогите Пете с реализацией устройства и выведите ответы на все запросы третьего типа.
В первой строке находится целое число $$$n\ (1 \leqslant n \leqslant 10^5)$$$ — число отрезков.
Далее в $$$n$$$ строках вводятся пары чисел — $$$a_i$$$ и $$$b_i\ (1 \leqslant a_i, b_i \leqslant 10^9)$$$ — координаты начала и конца отрезка $$$i$$$. Гарантируется, что все отрезки имеют одинаковую длину.
В следующей строке вводится число $$$q\ (1 \leqslant q \leqslant 10^5)$$$ — количество операций.
Далее в $$$q$$$ строках даны запросы. Первое число в строке $$$t\ (t \in \{1, 2, 3\})$$$ — тип операции.
Если $$$t = 1$$$, то далее идёт два числа $$$i\ (1 \leqslant i \leqslant n)$$$ и $$$d\ (0 \leqslant d \leqslant 10^9)$$$, а также символ «l» или «r». «l» означает сдвиг влево, а «r» — вправо.
Если $$$t = 2$$$, то далее идёт два числа $$$i$$$ и $$$j\ (1 \leqslant i \leqslant j \leqslant n)$$$, а также символ «l» или «r». «l» означает расширение влево, а «r» — вправо.
Если $$$t = 3$$$, то далее идёт число $$$i\ (1 \leqslant i \leqslant n)$$$.
Для каждого запроса третьего типа, если искомый отрезок найден, необходимо вывести два числа — координату начала и конца найденного отрезка через пробел. Если искомых отрезков несколько, можно вывести любой из них. В случае, если такого отрезка нет, выведите одно число $$$-1$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Обратите внимание, что подзадачи 4 и 5 не требуют прохождения теста из условия.
Здесь $$$C$$$ — ограничение на правую границу отрезка после каждого запроса. Например, если $$$C \leqslant 100$$$, то правая граница каждого отрезка не будет превосходить $$$100$$$ после каждого запроса.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи | Комментарий |
| $$$0$$$ | $$$0$$$ | — | — | Тесты из условия |
| $$$1$$$ | $$$10$$$ | $$$n \leqslant 100, C \leqslant 100$$$ | $$$0$$$ | — |
| $$$2$$$ | $$$10$$$ | $$$n \leqslant 1000, C \leqslant 1000$$$ | $$$1$$$ | — |
| $$$3$$$ | $$$10$$$ | $$$n \leqslant 1000, C \leqslant 10^9$$$ | $$$2$$$ | — |
| $$$4$$$ | $$$15$$$ | $$$n \leqslant 10^5, C \leqslant 10^9$$$ | — | Нет запросов первого типа |
| $$$5$$$ | $$$15$$$ | $$$n \leqslant 10^5, C \leqslant 10^9$$$ | — | Нет запросов второго типа |
| $$$6$$$ | $$$40$$$ | $$$n \leqslant 10^5, C \leqslant 10^9$$$ | $$$3, 4, 5$$$ | — |
31 43 610 1353 12 2 2 r1 2 1 l2 2 2 r3 3
-1 2 14
В тесте из условия изначально у нас имеются отрезки $$$[1; 4], [3; 6], [10; 13]$$$ и поступает 5 запросов.
- Первый запрос требует от нас найти отрезок, содержащий в себе первый, т.е. $$$[1; 4]$$$. Такого отрезка нет, поэтому ответ на запрос $$$-1$$$.
- Второй запрос расширяет отрезок номер два вправо, он становится равным $$$[3; 9]$$$.
- Третий запрос сдвигает отрезок номер два влево на $$$1$$$, он становится равным $$$[2; 8]$$$.
- Четвертый запрос расширяет отрезок номер два вправо, он становится равным $$$[2; 14]$$$.
- Пятый запрос требует от нас найти отрезок, содержащий в себе третий, т.е. $$$[10; 13]$$$. Это отрезок $$$[2; 14]$$$, мы выводим его в качестве ответа на запрос.