Камила и Динара играют в «Wordle». Камила загадала слово длины $$$n$$$, состоящее из различных латинских букв. Динара сделала одну попытку угадать и назвала слово длины $$$n$$$, также состоящее из различных латинских букв. Камила раскрасила буквы в догадке Динары в соответствии со следующими правилами:
Например, если было загадано слово ALERT, а догадка была ALONE, то буквы будут раскрашены в цвета GGWWY. Первые две буквы в словах совпадают, поэтому они зеленые. Буква E есть в загаданном слове, но находится на другой позиции, поэтому она жёлтая. Остальные буквы белые, так как их нет в загаданном слове.
Проснувшись следующим утром, Динара увидела, что буквы в ее слове не разобрать, так как они закрашены гуашью. Динара поняла, что забыла свою догадку. Помогите ей и определите, существует ли слово из различных букв, которое было бы раскрашено таким образом, и если существует, выведите любое такое слово.
В первой строке вводится одно целое число $$$n$$$ $$$(1 \le n \le 10)$$$ — длина загаданного слова.
Во второй строке вводится строка длины $$$n$$$, состоящая из заглавных латинских букв — загаданное слово. Гарантируется, что все буквы в нем различны.
В третьей строке вводится строка длины $$$n$$$, состоящая из букв G, Y, W — цвета, в которые были раскрашены буквы в слове Динары.
Если подходящих слов не существует, выведите No.
Если хотя бы одно подходящее слово существует, в первой строке выведите Yes, во второй — любое подходящее слово.
В данной задаче 20 тестов, помимо тестов из условия, каждый из них оценивается в 5 баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
6 ABCDEF WYGGYW
Yes HECDBG
2 AB GY
No
2 EV GG
Yes EV
Разберем первый пример из условия.
Буквы H и G не встречаются в загаданном слове, поэтому они белые.
Буквы E и B встречаются, но на других позициях, поэтому они жёлтые
Буквы C и D совпадают с буквами на соответствующих позициях в загаданном слове, поэтому они зелёные.
Есть и другие ответы, любой правильный ответ будет зачтен.
Обратите внимание, что строка HECDBH не является ответом, так как в ней есть совпадающие буквы.
Однажды во время прогулки Алина увидела длинное число, которое кто-то написал на асфальте. Алина захотела найти положительное число такой же длины без ведущих нулей, чтобы сумма этих двух чисел была палиндромом.
Число называется палиндромом, если оно читается одинаково справа налево и слева направо. Например, числа $$$121, 66, 98989$$$ являются палиндромами, а $$$103, 239, 1241$$$ — нет.
После некоторых размышлений Алина поняла, что такое число всегда можно найти. Помогите Алине найти подходящее число!
В первой строке вводится одно целое число $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — длина числа, которое увидела Алина.
Во второй строке вводится одно положительное целое число длины $$$n$$$. Гарантируется, что оно не содержит ведущих нулей.
Выведите ответ на задачу — положительное целое число без ведущих нулей длины $$$n$$$, такое что его сумма с числом из входных данных будет палиндромом.
Если таких чисел несколько, вы можете вывести любое из них.
В данной задаче 25 тестов, помимо тестов из условия, каждый из них оценивается в 4 балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие в случае $$$n \leq 6$$$, наберут не менее 20 баллов.
Решения, корректно работающие в случае, когда существует ответ, отличающийся от $$$10^n$$$ не более чем на 100, наберут не менее 24 баллов.
2 99
32
4 1023
8646
3 385
604
В первом примере из условия $$$99 + 32 = 131$$$ — палиндром. Число $$$12$$$ также будет являться ответом, так как $$$99 + 12 = 111$$$.
Во втором примере из условия $$$1023 + 8646 = 9669$$$.
В третьем примере из условия $$$385 + 604 = 989$$$.
Маленький Леон живет в лесу. Недавно он заметил, что некоторые деревья возле его любимой тропинки засыхают, а другие наоборот слишком увлажнены. Леон очень любит свой лес, поэтому решил научиться контролировать уровень влажности почвы, чтобы спасти деревья.
Возле тропинки растут $$$n$$$ деревьев, текущие уровни влажности которых заданы массивом $$$a_1, a_2, \dots, a_n$$$. Леон научился трем способностям, которые помогут ему осушать и поливать почву.
Леон хочет узнать минимальное число действий, которое необходимо совершить, чтобы каждое дерево имело уровень влажности равный $$$0$$$.
В первой строке вводится одно целое число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$).
Во второй строке вводятся $$$n$$$ целых чисел $$$a_1, a_2 \ldots a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — изначальные уровни влажности деревьев.
Выведите одно целое число — минимальное число действий.
В данной задаче 25 тестов, помимо тестов из условия, каждый из них оценивается в 4 балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие на упорядоченном по неубыванию массиве, наберут не менее $$$28$$$ баллов.
Решения, корректно работающие на массивах, которые до некоторой позиции убывают, а после нее возрастают, наберут не менее $$$44$$$ баллов.
Решения, корректно работающие на массиве с не более, чем одним не нулем, наберут не менее $$$16$$$ баллов.
3 -2 -2 -2
2
3 10 4 7
13
В первом примере из условия достаточно $$$2$$$ раза применить операцию прибавления $$$1$$$ ко всему массиву.
Во втором примере из условия можно $$$4$$$ раза применить операцию вычитания на префиксе длины $$$3$$$ и получить массив $$$6, 0, 3$$$.
После этого $$$6$$$ раз применить операцию вычитания на префиксе длины $$$1$$$ и $$$3$$$ раза операцию вычитания на суффиксе длины $$$1$$$. Итого, количество действий составит $$$4 + 6 + 3 = 13$$$. Можно показать, что меньшим количеством действий обойтись нельзя, поэтому $$$13$$$ — это ответ.
Недавно в Диваново построили огромную шлюзовую систему. Всего было построено $$$n$$$ шлюзов, $$$i$$$-й из них имеет объем $$$v_i$$$ литров. Изначально все шлюзы пусты. В каждый шлюз ведет труба, при открытии которой в шлюз будет поступать по $$$1$$$ литру воды в секунду. Исходно все трубы закрыты.
Шлюзовая система устроена так, что если доливать воду в $$$i$$$-й шлюз сверх его объема, она будет моментально моментально переливаться в шлюз с номером $$$i + 1$$$. Если шлюз c номером $$$i + 1$$$ тоже заполнен, вода будет переливаться дальше. Вода из последнего шлюза будет выливаться в озеро.
Рисунок показывает $$$5$$$ шлюзов с открытыми трубами к шлюзам $$$1$$$ и $$$3$$$. Так как шлюзы $$$1$$$, $$$3$$$ и $$$4$$$ уже заполнены, фактически вода идет в шлюзы $$$2$$$ и $$$5$$$.
Для того, чтобы шлюзы начали функционировать, необходимо заполнить каждый из них. Мэра Дивановской области интересует $$$q$$$ независимых запросов. Для каждого запроса предположим, что изначально все шлюзы пусты и все трубы закрыты, затем одновременно открываются несколько труб. Для $$$j$$$-го запроса мэр хочет знать, какое минимальное число труб надо включить, чтобы не позже чем через $$$t_j$$$ секунд все шлюзы стали заполнены.
Помогите мэру справиться с этой сложной задачей и ответьте на все его запросы!
В первой строке вводится одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество шлюзов.
Во второй строке вводятся $$$n$$$ целых чисел $$$v_1, v_2, \dots, v_n$$$ ($$$1 \le v_i \le 10^9$$$) — объемы шлюзов.
В третьей строке вводится одно целое число $$$q$$$ ($$$1 \le q \le 200\,000$$$) — число запросов.
В следующих $$$q$$$ строках вводится по одному целому числу $$$t_i$$$ ($$$1 \le t_j \le 10^9$$$) — время, за которое нужно наполнить все шлюзы в $$$j$$$-м запросе.
Выведите $$$q$$$ чисел, $$$j$$$-е из них должно быть равно минимальному числу труб, которое нужно открыть, чтобы наполнить все шлюзы за время $$$t_j$$$. Если за это время наполнить всю шлюзы невозможно, выведите $$$-1$$$.
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | |||||||
| Группа | Баллы | $$$n$$$ | $$$q$$$ | $$$v_i$$$ | $$$t_j$$$ | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия. |
| 1 | 17 | $$$n \le 50$$$ | $$$q \le 50$$$ | $$$v_i \le 100$$$ | $$$t_j \le 100$$$ | 0 | |
| 2 | 14 | – | – | – | – | – | Все $$$v_i$$$ равны. |
| 3 | 19 | $$$n \le 300$$$ | $$$q \le 300$$$ | – | – | 0, 1 | |
| 4 | 24 | $$$n \le 5000$$$ | $$$q \le 5000$$$ | – | – | 0, 1, 3 | |
| 5 | 26 | – | – | – | – | 0 – 4 | |
5 4 1 5 4 1 6 1 6 2 3 4 5
-1 3 -1 -1 4 3
5 4 4 4 4 4 6 1 3 6 5 2 4
-1 -1 4 4 -1 5
В первом примере $$$6$$$ запросов:
В запросах $$$1, 3, 4$$$ ответ $$$-1$$$. Чтобы заполнить первый шлюз нужно подождать $$$4$$$ секунды, даже если открыты все трубы.
В шестом запросе можно открыть трубы в шлюзах $$$1, 3$$$, и $$$4$$$. Тогда через $$$4$$$ секунды заполнятся шлюзы $$$1$$$ и $$$4$$$. Через $$$1$$$ секунду $$$1$$$ литр воды перельётся в шлюзы $$$2$$$ и $$$5$$$. Шлюз $$$3$$$ будет заполнен своей трубой.
Аналогично во втором запросе можно открыть трубы в шлюзах $$$1, 3$$$ и $$$4$$$.
В пятом запросе можно открыть трубы в шлюзах с номерами $$$1, 2, 3, 4$$$.
Маленький пират Серёжа скачал игру с разными видами головоломок. Среди них ему понравилась лишь одна, самая сложная.
Головоломка представляет из себя таблицу из $$$n$$$ строк и $$$m$$$ столбцов, в ячейках которой записаны числа от $$$1$$$ до $$$n \cdot m$$$ по одному разу.
Чтобы собрать головоломку, нужно выбрать последовательность клеток таблицы, в которой любые две подряд идущие клетки соседние по стороне в таблице. Последовательность может иметь произвольную длину, и каждая клетка может встречаться в последовательности произвольное число раз. Для клетки со значением $$$i$$$ рассмотрим позицию $$$t_i$$$ — позицию первого вхождения клетки с таким значением в последовательность. Последовательность решит головоломку, если каждая клетка таблицы встречается в ней, и $$$t_1 \lt t_2 \lt \dots \lt t_{nm}$$$. Другими словами, последовательность должна в первый раз посетить клетку со значением $$$x$$$ до клетки со значением $$$x + 1$$$ для всех $$$x$$$.
Назовем головоломку решаемой, если для нее существует хотя бы одна подходящая последовательность.
Серёжа понял, что не любая головоломка решаемая, так как подходящей последовательности может не существовать. Ему стало интересно, можно ли немного изменить головоломку, чтобы ее можно было решить. На это Серёже не хватило таланта, поэтому ему нужна ваша помощь.
За одно действие Сережа может выбрать две произвольных клетки (не обязательно соседние по стороне) и поменять числа, записанные в них. Он хотел бы знать минимальное число действий, которое потребуется, чтобы головоломка стала решаемой, но очень нетерпелив. Поэтому найдите, равняется ли минимальное число действий $$$0$$$, $$$1$$$, или же не менее $$$2$$$. В случае, когда потребуется ровно $$$1$$$ действие, найдите также количество подходящих пар клеток для обмена чисел.
В первой строке вводятся два целых положительных числа $$$n, m$$$ ($$$1 \leq n \cdot m \leq 400\,000$$$) — длины сторон таблицы.
В каждой из следующих $$$n$$$ строках вводятся $$$m$$$ целых чисел $$$a_{i1}, a_{i2}, \dots, a_{im}$$$ ($$$1 \le a_{ij} \le n \cdot m$$$).
Гарантируется, что каждое число от $$$1$$$ до $$$n \cdot m$$$ встречается ровно один раз.
Пусть $$$a$$$ — минимальное число действий, после которых головоломка станет решаемой.
Если $$$a = 0$$$, выведите $$$0$$$.
Если $$$a = 1$$$, выведите $$$1$$$, а также количество подходящих пар клеток.
Если $$$a \ge 2$$$, выведите $$$2$$$.
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | ||||
| Группа | Баллы | $$$n \cdot m$$$ | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 14 | $$$n \cdot m \leq 100$$$ | – | $$$n = 1$$$ |
| 2 | 19 | $$$n \cdot m \leq 100$$$ | 0, 1 | |
| 3 | 17 | $$$n \cdot m \le 2000 $$$ | 1 | $$$n = 1$$$ |
| 4 | 13 | $$$n \cdot m \le 2000$$$ | 0 – 3 | |
| 5 | 16 | – | 1, 3 | $$$n = 1$$$ |
| 6 | 21 | – | 0 – 5 |
3 3 2 1 3 6 7 4 9 8 5
0
2 3 1 6 4 3 2 5
1 3
1 6 1 6 5 4 3 2
2
В первом примере из условия последовательность клеток $$$(1, 2), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3)$$$, $$$(2, 3), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (3, 2), (3, 1)$$$ решает головоломку, поэтому ответ $$$0$$$.
Головоломка во втором примере из условия не решается, но будет решаться после любого из трех обменов клеток со значениями $$$(1, 5), (1, 6), (2, 6)$$$.
В третьем примере из условия потребуется не менее двух обменов, поэтому ответ равен $$$2$$$.
Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из $$$2$$$ строк и $$$n$$$ столбцов, каждый элемент которой $$$0$$$ или $$$1$$$. За один ход можно поменять местами два элемента, стоящие в соседних клетках.
Более формально, будем считать, что строки матриц пронумерованы сверху вниз от $$$1$$$ до $$$2$$$, а столбцы — слева направо от $$$1$$$ до $$$n$$$. Обозначим клетку на пересечении строки $$$x$$$ и столбца $$$y$$$ за $$$(x, y)$$$. Будем считать две клетки $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ соседними, если $$$|x_1 - x_2| + |y_1 - y_2| = 1$$$.
Алисе не нравится, какой рисунок образуют клетки пазла в данный момент. Она придумала свой рисунок, с которым и планирует подарить Ибрагиму новый пазл, но для этого нужно привести пазл в соответствующее состояние.
В конце учебного года у Алисы очень плотное расписание, и она не хочет тратить на эту задачу много времени. Помогите Алисе найти минимальное количество ходов, за которое она может получить свой рисунок, или скажите, что это невозможно.
В первой строке вводится одно целое число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — количество столбцов в пазле.
Следующие две строки описывают рисунок, образованный пазлом в данный момент. В каждой строке вводятся $$$n$$$ целых чисел, каждое из которых равно $$$0$$$ или $$$1$$$.
Следующие две строки описывают желаемый рисунок Алисы в том же формате.
Если Алиса не ошиблась и её рисунок можно получить, найдите и выведите минимальное необходимое количество ходов, иначе выведите $$$-1$$$.
Тесты к этой задаче состоят из 8 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | ||||
| Группа | Баллы | $$$n$$$ | Необходимые группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 16 | $$$n \le 7$$$ | 0 | |
| 2 | 11 | $$$n \le 17$$$ | 0, 1 | |
| 3 | 14 | $$$n \le 50$$$ | 0 – 2 | |
| 4 | 8 | $$$n \le 300$$$ | 0 – 3 | |
| 5 | 16 | $$$n \le 3000$$$ | 0 – 4 | |
| 6 | 16 | – | – | Вторая строка каждого пазла состоит из нулей. |
| 7 | 9 | – | 6 | Вторая строка второго пазла состоит из нулей. |
| 8 | 10 | – | 0 – 7 |
5 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0
5
3 1 0 0 0 0 0 0 0 0 0 0 0
-1
В первом примере из условия подойдет следующая последовательность обменов:
$$$(2, 1), (1, 1)$$$
$$$(1, 2), (1, 3)$$$
$$$(2, 2), (2, 3)$$$
$$$(1, 4), (1, 5)$$$
$$$(2, 5), (2, 4)$$$
Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен $$$5$$$.
Во втором примере из условия никакая последовательность ходов не приводит пазл к нужному виду.