Задано целое положительное число $$$n$$$. За $$$1$$$ ход можно выбрать любую его цифру и удалить её (т. е. выбирается некоторая позиция в числе и удаляется стоящая в этой позиции цифра). Операцию нельзя произвести, если осталась всего одна цифра. Если получившееся число содержит ведущие нули, то они автоматически удаляются.
Например, если из числа $$$32925$$$ удалить $$$3$$$-ю цифру, то результатом операции станет число $$$3225$$$, а если из числа $$$20099050$$$ удалить первую цифру, то результатом операции станет число $$$99050$$$ (следующие за первой цифрой $$$2$$$ нуля удаляются автоматически).
Какое наименьшее число ходов необходимо совершить, чтобы получившееся число делилось на $$$25$$$ и было положительным? Гарантируется, что для всех $$$n$$$, заданных во входных данных, ответ существует. Гарантируется, что число $$$n$$$ задано без ведущих нулей.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей одно целое число $$$n$$$ ($$$25 \le n \le 10^{18}$$$). Гарантируется, что для всех $$$n$$$, заданных во входных данных, ответ существует. Гарантируется, что число $$$n$$$ задано без ведущих нулей.
Для каждого набора входных данных в отдельной строке выведите целое число $$$k$$$ ($$$k \ge 0$$$) — наименьшее число ходов, которые нужно сделать, чтобы число стало делиться на $$$25$$$.
5 100 71345 3259 50555 2050047
0 3 1 3 2
В первом наборе входных данных уже задано число, которое делится на $$$25$$$.
Во втором наборе входных данных можно удалить цифры $$$1$$$, $$$3$$$ и $$$4$$$, тогда получится число $$$75$$$.
В третьем наборе входных данных достаточно удалить последнюю цифру — получится число $$$325$$$.
В четвёртом наборе входных данных необходимо удалить три последние цифры — получится число $$$50$$$.
В пятом наборе входных данных достаточно удалить цифры $$$4$$$ и $$$7$$$.
Дана шахматная доска размера $$$n$$$ на $$$n$$$. Клетка на пересечении $$$i$$$-й сверху ряду и $$$j$$$-го слева столбца обозначается как $$$(i,j)$$$.
На данный момент у Грегора есть несколько пешек в $$$n$$$-м ряду. Также в $$$1$$$-м ряду стоят вражеские пешки. За один шаг Грегор перемещает одну из своих пешек. Пешка может ходить на одну клетку вверх (из $$$(i,j)$$$ в $$$(i-1,j)$$$), если клетка назначения не занята другой пешкой. В дополнение, пешка может переместиться на одну клетку вверх по диагонали (из $$$(i,j)$$$ в $$$(i-1,j-1)$$$ или в $$$(i-1,j+1)$$$), если и только если в этой клетке стоит вражеская пешка. Вражеская пешка в таком случае убирается с доски.
Грегор хочет узнать, какое максимальное количество его пешек может достичь $$$1$$$-го ряда.
Заметьте, что в этой игре ходит только Грегор, вражеские пешки никогда не перемещаются. Также, когда пешка Грегора достигает $$$1$$$-го ряда, она останавливается и больше не может перемещаться.
Первая строка ввода содержит одно целое число $$$t$$$ ($$$1\le t\le 2\cdot 10^4$$$) — количество наборов входных данных. Далее следует описание этих $$$t$$$ наборов.
Каждый набор входных данных состоит из трех строк. Первая строка содержит одно целое число $$$n$$$ ($$$2\le n\le 2\cdot{10}^{5}$$$) — размер доски.
Вторая строка содержит бинарную строку длины $$$n$$$, в которой $$$1$$$ на $$$i$$$-й позиции соответствует вражеской пешке в $$$i$$$-й слева клетке в первом ряду, а $$$0$$$ соответствует пустой клетке.
Третья строка содержит бинарную строку длины $$$n$$$, в которой $$$1$$$ на $$$i$$$-й позиции соответствует пешке Грегора в $$$i$$$-й слева клетке в последнем ряду, а $$$0$$$ соответствует пустой клетке.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных меньше $$$2\cdot{10}^{5}$$$.
Для каждого набора входных данных выведите одно целое число: максимальное количество пешек Грегора, которые могут достичь $$$1$$$-го ряда.
4 3 000 111 4 1111 1111 3 010 010 5 11001 00000
3 4 0 0
В первом примере Грегор может просто переместить вперед все его $$$3$$$ пешки. Таким образом, ответ равен $$$3$$$.
Во втором примере Грегор может гарантировать, что все его $$$4$$$ пешки достигнут вражеского ряда, следуя раскрашенным путям как показано ниже. Помните — только Грегор делает ходы в этой «игре»!
В третьем примере единственная пешка Грегора застряла перед вражеской пешкой и не может достигнуть желаемого ряда.
В четвертом примере у Грегора нет пешек, поэтому ответ равен $$$0$$$.
Дана сетка $$$a$$$ размера $$$n \times m$$$ из неотрицательных целых чисел, где $$$a_{i,j}$$$ представляет глубину воды в $$$i$$$-й строке и $$$j$$$-м столбце.
Озеро — это набор ячеек, таких что:
- Каждая ячейка в наборе имеет $$$a_{i,j} \gt 0$$$
- Существует путь между любой парой ячеек в озере, двигаясь вверх, вниз, влево или вправо, несколько раз и не наступая на ячейку с $$$a_{i,j} = 0$$$.
Объем озера — это сумма глубин всех ячеек в озере.
Найдите наибольший объем озера в сетке.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных в тесте.
Первая строка каждого набора содержит два целых числа $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$) — размеры сетки.
Затем следуют $$$n$$$ строк, каждая из которых содержит $$$m$$$ целых чисел $$$a_{i,j}$$$ ($$$0 \leq a_{i,j} \leq 1000$$$) — глубина воды в каждой ячейке.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам не превышает $$$10^6$$$.
Для каждого теста выведите одно целое число — наибольший объем озера в сетке.
53 31 2 03 4 00 0 51 103 30 1 11 0 11 1 15 51 1 1 1 11 0 0 0 11 0 5 0 11 0 0 0 11 1 1 1 15 51 1 1 1 11 0 0 0 11 1 4 0 11 0 0 0 11 1 1 1 1
10 0 7 16 21
У Тимофея в саду растёт яблоня, она представляет собой корневое дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$ (вершины пронумерованы от $$$1$$$ от $$$n$$$). Деревом называется связный граф без циклов, петель и кратных ребер.
Это дерево очень необычное — оно растёт корнем вверх. Впрочем, в этом нет ничего необычного для деревьев в программировании.
Яблоня достаточно молодая, поэтому на ней вырастет всего два яблока. Яблоки вырастут в определённых вершинах (эти вершины могу совпадать). После того как яблоки вырастут, Тимофей начнёт трясти яблоню, пока яблоки не упадут. Каждый раз, когда Тимофей трясёт яблоню, с каждым из яблок происходит следующее:
Пусть яблоко сейчас находится в вершине $$$u$$$.
- Если у вершины $$$u$$$ есть ребёнок, то яблоко перемещается в него (если таких вершин несколько, то яблоко может переместиться в любую из них).
- Иначе яблоко падает с дерева.
Можно показать, что через конечное время оба яблока упадут с дерева.
У Тимофея есть $$$q$$$ предположений, в каких вершинах могут вырасти яблоки. Он предполагает, что яблоки могут вырасти в вершинах $$$x$$$ и $$$y$$$, и хочет узнать количество пар вершин ($$$a$$$, $$$b$$$), с которых яблоки могут упасть с дерева, где $$$a$$$ — вершина, с которой упадёт яблоко из вершины $$$x$$$, $$$b$$$ — вершина, с которой упадёт яблоко из вершины $$$y$$$. Помогите ему это сделать.
В первой строке дано число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных даны числа $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — количество вершин в яблоне.
Далее следует $$$n - 1$$$ строка, описывающая дерево. В $$$i$$$-й из них даны числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — ребро в дереве.
В следующей строке дано единственное целое число $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — количество предположений Тимофея.
Далее следует $$$q$$$ строк, описывающих предположения Тимофея. В $$$i$$$-й строке даны числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) — предполагаемые вершины, на которых вырастут яблоки.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$. Аналогично, сумма $$$q$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого запроса Тимофея выведите количество упорядоченных пар вершин, с которых яблоки могут упасть с дерева, если предположение окажется верным, в отдельной строке.
251 23 45 33 243 45 14 41 331 21 331 12 33 1
2 2 1 4 4 1 2
255 11 22 34 325 55 153 25 32 14 234 32 14 2
1 2 1 4 2
В первом примере:
- Для первого запроса существует две возможные пары вершин, с которых яблоки могут упасть: $$$(4, 4), (5, 4)$$$.
- Для второго запроса также существует две пары: $$$(5, 4), (5, 5)$$$.
- Для третьего запроса есть всего одна пара: $$$(4, 4)$$$.
- Для четвертого запроса существует $$$4$$$ пары: $$$(4, 4), (4, 5), (5, 4), (5, 5)$$$.
Дерево из первого примера. Во втором примере для первого предположения есть $$$4$$$ возможных пар вершин, с которых могут упасть яблоки: $$$(2, 3), (2, 2), (3, 2), (3, 3)$$$. Для второго запроса есть всего одна возможная пара: $$$(2, 3)$$$. Для третьего запроса есть две пары: $$$(3, 2), (3, 3)$$$.
Монокарп играет в компьютерную игру. Сейчас он хочет пройти первый уровень этой игры.
Уровень — это прямоугольное клеточное поле из $$$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$$$.
Помогите Монокарпу определить, можно ли пройти уровень.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют сами наборы входных данных, каждый из которых состоит из трех строк.
В первой строке задано одно целое число $$$n$$$ ($$$3 \le n \le 100$$$) — количество столбцов.
Далее следуют две строки, описывающие уровень. $$$i$$$-я из этих строк описывает $$$i$$$-ю строку уровня — строка состоит из символов 0 и 1. Символ 0 соответствует безопасной клетке, символ 1 — клетке с ловушкой.
Дополнительное ограничение на входные данные: клетки $$$(1, 1)$$$ и $$$(2, n)$$$ — безопасные.
Для каждого набора входных данных выведите YES, если уровень можно пройти, и NO, если нельзя.
4 3 000 000 4 0011 1100 4 0111 1110 6 010101 101010
YES YES NO 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$$$ самородков. За одну операцию вы можете сделать следующее:
- Разделить любую кучу на две кучи так, чтобы одна из полученных куч содержала в два раза больше золотых самородков, чем другая. (Все кучи должны содержать целое число самородков.)
Одно из возможных действий - взять кучу размера $$$6$$$ и разделить ее на кучи размеров $$$2$$$ и $$$4$$$, что является допустимым, так как $$$4$$$ в два раза больше, чем $$$2$$$.
Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных в тесте.
Единственная строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 10^7$$$) — начальный и целевой размер кучи соответственно.
Для каждого теста выведите «YES», если вы можете создать кучу размером ровно $$$m$$$, и «NO» в противном случае.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
116 49 44 218 2727 427 227 101 13 15 1746001 2984004
YES YES NO NO YES YES NO YES YES NO NO
Первый тест изображен в условии. Мы можем создать кучу размером $$$4$$$.
Во втором тесте мы можем выполнить следующие операции: $$$\{\color{red}{9}\} \to \{\color{red}{6},3\} \to \{4,2,3\}$$$. Куча, которая разделяется, выделена красным цветом перед каждой операцией.
В третьем тесте мы не можем выполнить ни одной операции.
В четвертом тесте мы не можем получить кучу большего размера, чем у нас изначально.
Вам дано подвешенное дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Корнем является вершина $$$1$$$. Также есть строка $$$s$$$, задающая цвета всех вершин: если $$$s_i = \texttt{B}$$$, то вершина $$$i$$$ чёрная, а если $$$s_i = \texttt{W}$$$, то вершина $$$i$$$ белая.
Поддерево дерева называется сбалансированным, если количество белых вершин поддерева равняется количеству чёрных вершин поддерева. Посчитайте количество сбалансированных поддеревьев.
На картинке дерево при $$$n=7$$$, $$$a=[1,1,2,3,3,5]$$$ и $$$s=\texttt{WBBWWBW}$$$. Поддерево вершины $$$3$$$ сбалансированно. Дерево — это связный граф без циклов. Подвешенное дерево — это дерево с выбранной вершиной, которую называют корнем. В этой задаче корнем каждого дерева является вершина $$$1$$$.
Дерево описано массивом предков $$$a_2, \dots, a_n$$$, содержащим $$$n-1$$$ число: $$$a_i$$$ — предок вершины с номером $$$i$$$ для всех $$$i = 2, \dots, n$$$. Предок вершины $$$u$$$ это следующая вершина на простом пути от $$$u$$$ к корню. Поддерево вершины $$$u$$$ — это множество всех вершин, которые содержат $$$u$$$ в пути к корню. Например на картинке выше, $$$7$$$ в поддереве у $$$3$$$, потому что простой путь $$$7 \to 5 \to 3 \to 1$$$ проходит через $$$3$$$. Обратите внимание, что сама вершина входит в своё поддерево, и поддеревом корня является всё дерево.
Первая строка входных данных содержит число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит число $$$n$$$ ($$$2 \le n \le 4000$$$) — количество вершин в дереве.
Вторая строка каждого набора содержит $$$n-1$$$ число $$$a_2, \dots, a_n$$$ ($$$1 \le a_i \lt i$$$) — родители вершин $$$2, \dots, n$$$.
Третья строка каждого набора содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов $$$\texttt{B}$$$ и $$$\texttt{W}$$$ — раскраска дерева.
Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно число — количество сбалансированных поддеревьев.
371 1 2 3 3 5WBBWWBW21BW81 2 3 4 5 6 7BWBWBWBW
2 1 4
Первый пример изображён в условии. Только поддеревья вершин $$$2$$$ и $$$3$$$ сбалансированны.
Во втором примере только поддерево вершины $$$1$$$ сбалансированно.
в третьем примере сбалансированны поддеревья вершин $$$1$$$, $$$3$$$, $$$5$$$ и $$$7$$$.
Алиса и Боб играют в следующую игру. У Алисы есть набор непересекающихся отрезков целых чисел $$$S$$$, изначально содержащий только один отрезок $$$[1, n]$$$. За один ход Алиса выбирает некоторый отрезок $$$[l, r]$$$ из набора $$$S$$$, а Боб выбирает некоторое число $$$d$$$ из этого отрезка ($$$l \le d \le r$$$). Затем Алиса убирает $$$[l, r]$$$ из $$$S$$$, и добавляет в $$$S$$$ отрезки $$$[l, d - 1]$$$ (если $$$l \le d - 1$$$) и $$$[d + 1, r]$$$ (если $$$d + 1 \le r$$$). Игра заканчивается, когда $$$S$$$ становится пустым. Можно показать, что количество шагов в такой игре всегда ровно $$$n$$$.
После того, как игра была сыграна, Алиса запомнила все отрезки $$$[l, r]$$$, которые она доставала из набора $$$S$$$, но Боб не запомнил ни одного числа, которые он выбирал. Но Боб умный и понимает, что числа $$$d$$$ можно восстановить, используя отрезки, которые помнит Алиса, и просит вас помочь запрограммировать это.
По данному списку отрезков, которые Алиса доставала ($$$[l, r]$$$) восстановите для каждого отрезка число $$$d$$$, которое выбирал Боб.
Можно показать, что по данному списку отрезков всегда существует ровно один способ восстановить числа Боба.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$).
Каждая из следующих $$$n$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$), обозначающих, что Алиса в какой-то момент игры выбрала отрезок $$$[l, r]$$$.
Обратите внимание, что отрезки даны в произвольном порядке.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$, а отрезки в каждом наборе входных данных соответствуют корректной игре.
Для каждого набора входных данных выведите $$$n$$$ строк. Каждая строка должна содержать три целых числа $$$l$$$, $$$r$$$ и $$$d$$$, обозначающих, что для отрезка Алисы $$$[l, r]$$$ Боб выбрал число $$$d$$$.
Вы можете выводить эти строки в любом порядке. Можно показать, что ответ единственный.
Не обязательно выводить пустую строку между различными входными данными. В примере эти пустые строки сделаны только для удобства.
4 1 1 1 3 1 3 2 3 2 2 6 1 1 3 5 4 4 3 6 4 5 1 6 5 1 5 1 2 4 5 2 2 4 4
1 1 1 1 3 1 2 2 2 2 3 3 1 1 1 3 5 3 4 4 4 3 6 6 4 5 5 1 6 2 1 5 3 1 2 1 4 5 5 2 2 2 4 4 4
В первом примере есть только один отрезок $$$[1, 1]$$$. Алиса выбирала только один отрезок $$$[1, 1]$$$, и Боб мог выбрать только число $$$1$$$.
Во втором примере $$$n = 3$$$. Изначально в наборе находится один отрезок $$$[1, 3]$$$.
- Алиса выбирает отрезок $$$[1, 3]$$$. Боб выбирает число $$$1$$$. Алиса добавляет в набор отрезок $$$[2, 3]$$$, и после этого хода это единственный отрезок в наборе.
- Алиса выбирает отрезок $$$[2, 3]$$$. Боб выбирает число $$$3$$$. Алиса добавляет в набор отрезок $$$[2, 2]$$$.
- Алиса выбирает отрезок $$$[2, 2]$$$. Боб выбирает число $$$2$$$. Игра заканчивается.
В четвертом наборе игра начинается с $$$n = 5$$$. Изначально в наборе находится только отрезок $$$[1, 5]$$$. Ходы в игре показаны в следующей таблице.
| Номер хода | Отрезок, выбранный Алисой | Число, выбранное Бобом | Набор отрезков после хода |
| Перед началом | $$$ \{ [1, 5] \} $$$ | ||
| 1 | $$$[1, 5]$$$ | $$$3$$$ | $$$ \{ [1, 2], [4, 5] \}$$$ |
| 2 | $$$[1, 2]$$$ | $$$1$$$ | $$$ \{ [2, 2], [4, 5] \} $$$ |
| 3 | $$$[4, 5]$$$ | $$$5$$$ | $$$ \{ [2, 2], [4, 4] \} $$$ |
| 4 | $$$[2, 2]$$$ | $$$2$$$ | $$$ \{ [4, 4] \} $$$ |
| 5 | $$$[4, 4]$$$ | $$$4$$$ | $$$ \{ \} $$$ (пустой набор) |
Дана матрица из $$$n$$$ строк и $$$m$$$ столбцов, каждая ячейка которой имеет один из трех типов:
- Пустая ячейка (обозначается как «.»).
- Камень (обозначается как «*»).
- Препятствие (обозначается как строчная буква латинского алфавита «o»).
Каждый камень начинает падать, пока не окажется на полу (в нижней строке матрицы), в ячейке над препятствием, или в ячейке над другим камнем, который уже закончил падение. (Другими словами, все камни начинают падать и падают, пока под ними пустые ячейки.)
Просимулируйте процесс и выведите состояние матрицы после того, как все камни закончат падать.
В первой строке задано целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следуют сами наборы входных данных.
В первой строке каждого набора входных данных заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 50$$$) — количество строк и столбцов в матрице.
Затем следуют $$$n$$$ строк, каждая из которых содержит $$$m$$$ символов. Каждый из этих символов — «.», «*» или «o» (пустая клетка, камень и препятствие соответственно).
Для каждого набора входных данных выведите матрицу из $$$n$$$ строк и $$$m$$$ столбцов, описывающую результат процесса.
Не обязательно выводить новую строку после каждого набора входных данных; в примерах из условия она выводится для наглядности.
3 6 10 .*.*....*. .*.......* ...o....o. .*.*....*. .......... .o......o* 2 9 ...***ooo .*o.*o.*o 5 5 ***** *.... ***** ....* *****
.......... ...*....*. .*.o....o. .*........ .*......** .o.*....o* ....**ooo .*o**o.*o ..... *...* ***** ***** *****