Как всем известно, 14 ноября празднуется День расслабленности и беззаботности. Петя решил провести этот день как положено и смотреть тикток, пока не кончится лента. Лента, конечно, никогда не кончается. Петю это не пугает, спать, есть и пить он сегодня всё равно не собирается. Мешают ему только телефоны, которые иногда разряжаются.
Телефоны Пете покупали $$$n$$$ лет подряд, по одному в год. Телефон, купленный в $$$i$$$-й год, на полном заряде работает ровно $$$a_i$$$ минут непрерывно, а потом его нужно ровно $$$b_i$$$ минут непрерывно заряжать. Пока телефон заряжается, смотреть с него нельзя. Зарядок дома сколько угодно, так что заряжаться могут хоть все телефоны сразу.
Петя смотрит тикток по кругу со всех доступных ему телефонов. Сначала он сам выбирает, в каком порядке их брать, и потом этот порядок не меняет. Когда телефон разряжается, Петя сразу ставит его на зарядку и берёт следующий, а после последнего снова берёт первый. В самом начале все телефоны заряжены.
Если подошла очередь телефона, который не успел зарядиться, просмотр прерывается и праздник испорчен. Если телефон зарядился ровно в тот момент, когда до него дошла очередь, его можно брать.
Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ ответьте, можно ли, взяв телефоны с $$$1$$$-го по $$$i$$$-й и выбрав порядок их использования, смотреть тикток непрерывно и вечно.
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество лет.
В $$$i$$$-й из следующих $$$n$$$ строк заданы два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i \le 10^9$$$, $$$0 \le b_i \le 10^9$$$) — сколько минут работает телефон, купленный в $$$i$$$-й год, и сколько минут он заряжается. Телефоны перечислены в порядке покупки.
Выведите $$$n$$$ строк. В $$$i$$$-й строке выведите YES, если, используя все телефоны, купленные за первые $$$i$$$ лет, Петя сможет смотреть тикток вечно, и NO иначе.
Ответ можно выводить в любом регистре (например, строки yEs, yes, Yes и YES будут засчитаны как положительный ответ).
42 12 11 1010 1
NO YES NO YES
При $$$i=1$$$ единственный телефон работает с $$$0$$$-й по $$$2$$$-ю минуту, затем заряжается, и смотреть не с чего. Ответ NO.
При $$$i=2$$$ первый телефон работает с $$$0$$$-й по $$$2$$$-ю минуту, второй — со $$$2$$$-й по $$$4$$$-ю, затем первый — с $$$4$$$-й по $$$6$$$-ю. Первый заряжен к $$$3$$$-й минуте, а второй к $$$6$$$-й тоже успевает зарядиться. Дальше они чередуются вечно без перерывов. Ответ YES.
При $$$i=3$$$ в порядке $$$1,2,3$$$ третий телефон работает с $$$4$$$-й по $$$5$$$-ю минуту и заряжается до $$$15$$$-й. Первый и второй работают ещё по разу до $$$9$$$-й минуты, когда снова нужен третий. Он ещё не заряжен; другие порядки тоже не подходят. Ответ NO.
При $$$i=4$$$ подходит порядок $$$1,2,3,4$$$: четвёртый телефон работает с $$$5$$$-й по $$$15$$$-ю минуту, пока заряжается третий. Дальше перерывов не будет. Ответ YES.
Как всем известно, 14 ноября празднуется День разбитых фонарей. Праздник неофициальный, но со смыслом: даже во тьме и среди осколков — неудач, перемен и тяжёлых периодов — всегда остаётся место для внутреннего света и нового начала. Лучше всех эту мысль понимают сами разбитые фонари: гаснуть насовсем они не собираются.
Во дворе стоят два разбитых фонаря. Раз они разбиты, то светят не постоянно, а мигают. Первый фонарь мигает каждые $$$a$$$ секунд, то есть в моменты $$$a, 2a, 3a, \ldots$$$, второй — каждые $$$b$$$ секунд, то есть в моменты $$$b, 2b, 3b, \ldots$$$. Если оба фонаря мигают в один и тот же момент, это считается за два мигания.
Под фонарями стоит электрик, который пришёл составить акт о неисправности, и считает мигания. К моменту $$$0$$$ он уже насчитал $$$c$$$ миганий, и каждое новое мигание увеличивает его счёт на единицу.
Найдите любое целое число $$$x \ge 1$$$, для которого через $$$x$$$ секунд после момента $$$0$$$ общее число насчитанных электриком миганий будет равно $$$x$$$.
В единственной строке заданы три целых числа $$$a$$$, $$$b$$$, $$$c$$$ ($$$2 \le a \le b \le 10^9$$$, $$$b \ge 3$$$, $$$1 \le c \le 10^9$$$) — периоды мигания первого и второго фонаря и число миганий, насчитанных электриком к моменту $$$0$$$.
Выведите одно целое число $$$x$$$ ($$$1 \le x \le 10^{18}$$$) — момент, в который счёт электрика равен $$$x$$$. Можно доказать, что такой момент всегда существует. Если подходящих моментов несколько, выведите любой.
3 4 5
10
В момент $$$10$$$ первый фонарь уже мигнул $$$3$$$ раза, а второй — $$$2$$$ раза, поэтому счёт электрика равен $$$5 + 3 + 2 = 10$$$, и этот момент подходит. В момент $$$11$$$ новых миганий нет, счёт всё ещё равен $$$10$$$ и отстаёт от времени. В момент $$$12$$$ мигают оба фонаря сразу, счёт становится $$$5 + 4 + 3 = 12$$$ и снова совпадает со временем. Подходят ровно два момента: $$$10$$$ и $$$12$$$, любой из них будет засчитан.
November 14 is Tartar Sauce Day in Japan. At a fried oyster festival, someone asked Aki for a little more sauce. Aki took the request seriously and ran pipes between the stalls.
There are $$$n$$$ stalls numbered from $$$1$$$ to $$$n$$$ in clockwise order. For $$$1 \le i \lt n$$$, pipe $$$i$$$ connects stalls $$$i$$$ and $$$i+1$$$. Pipe $$$n$$$ connects stalls $$$n$$$ and $$$1$$$.
Each stall $$$i$$$ has an integer $$$a_i$$$. If $$$a_i \gt 0$$$, the stall receives $$$a_i$$$ liters of sauce per second from outside the ring. If $$$a_i \lt 0$$$, then $$$-a_i$$$ liters of sauce per second are taken from the stall. For example, if $$$a_i = -3$$$, three liters per second are taken from the stall. If $$$a_i = 0$$$, no sauce is supplied or taken away at the stall.
For each pipe, you can choose the flow direction and a constant nonnegative integer flow rate in liters per second for free. The rate may be zero. Pipe $$$i$$$ can carry at most $$$b_i$$$ liters per second in either direction. You can replace pipe $$$i$$$ with one of unlimited capacity for $$$c_i$$$ units of money.
At each stall, the total inflow must equal the total outflow. This includes both the flows through the pipes and any sauce supplied or taken away at the stall. Find the minimum total cost of replacing pipes so that this requirement can be met.
The first line contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of stalls.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). It is guaranteed that $$$a_1 + a_2 + \cdots + a_n = 0$$$.
The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — the pipe capacities.
The fourth line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — the pipe replacement costs.
Output a single integer — the minimum total cost of replacing pipes.
It can be shown that a valid choice of flows always exists if all pipes are replaced.
44 -2 -1 -12 0 1 27 4 3 5
0
33 -2 -10 0 02 5 4
6
50 0 4 0 -40 0 0 0 01 2 7 8 3
6
30 0 00 4 02 3 5
0
42 0 -2 01 1 0 04 5 6 3
9
41000000000 -1 -1000000000 10 0 0 01000000000 1000000000 1000000000 1000000000
3000000000
In the first example, no pipes need to be replaced. Pipe $$$1$$$ can carry two liters per second from stall $$$1$$$ to stall $$$2$$$. Pipe $$$3$$$ can carry one liter per second from stall $$$4$$$ to stall $$$3$$$, and pipe $$$4$$$ can carry two liters per second from stall $$$1$$$ to stall $$$4$$$. There is no flow through pipe $$$2$$$.
In the second example, if any two pipes are left in place, their common stall has no flow through its pipes even though its $$$a_i$$$ is nonzero. You can keep pipe $$$2$$$ and send two liters per second from stall $$$1$$$ to stall $$$2$$$ and one liter per second from stall $$$1$$$ to stall $$$3$$$. This costs $$$2 + 4 = 6$$$.
In the third example, four liters per second must be sent from stall $$$3$$$ to stall $$$5$$$. The clockwise route requires replacing pipes $$$3$$$ and $$$4$$$ at a cost of $$$15$$$. The counterclockwise route requires replacing pipes $$$2$$$, $$$1$$$, and $$$5$$$ at a cost of $$$6$$$. The second route costs less.
In the fourth example, the flow rate in every pipe can be set to zero.
In the fifth example, stall $$$3$$$ must receive two liters per second from stall $$$1$$$. With the original pipes, the route through stall $$$2$$$ can carry at most one liter per second, and the route through stall $$$4$$$ cannot carry any sauce. Replacing just one pipe on a route does not increase its capacity. Replacing both pipes on either of these routes costs $$$9$$$ and lets the route carry the required amount.
In the sixth example, any two pipes with zero flow cut off a nonempty part of the ring whose sum of $$$a_i$$$ is nonzero. Therefore, at most one pipe can be kept. For example, if you keep pipe $$$4$$$, you can send $$$10^9$$$ and $$$10^9-1$$$ liters per second clockwise through pipes $$$1$$$ and $$$2$$$, respectively, and one liter per second counterclockwise through pipe $$$3$$$.
14 ноября в США отмечается День семейной пижамы.
Фабрика «Сонный енот» готовит комплекты для праздничной фотосессии. Директор уверен: два человека в одинаковых пижамах — это один человек, который очень быстро бегает. Поэтому в каждом семейном комплекте обязательно должна быть одна красная и одна синяя пижама.
На конвейере в ряд лежат $$$n$$$ пижам, пронумерованных слева направо от $$$1$$$ до $$$n$$$. Цвет $$$i$$$-й пижамы задан символом $$$s_i$$$: R означает красный цвет, а B — синий. Ценность этой пижамы равна $$$a_i$$$.
За одну операцию сотрудник может снять с конвейера любые две соседние пижамы разных цветов и собрать из них комплект. Ценность комплекта равна сумме ценностей этих двух пижам. После снятия пары оставшиеся части ряда соединяются: пижамы, между которыми была снятая пара, становятся соседними.
Можно выполнить любое число операций, в том числе ни одной. Найдите максимально возможную суммарную ценность собранных комплектов.
В первой строке задано целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — количество пижам на конвейере.
Во второй строке задана строка $$$s$$$ длины $$$n$$$, состоящая из символов R и B, — цвета пижам слева направо.
В третьей строке заданы $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — ценности пижам.
Выведите одно целое число — максимально возможную суммарную ценность собранных комплектов.
2RB5 9
14
7RRBBRRR100 1 3 4 1 100 1
108
4BBBB1 10 100 1000
0
В первом примере две пижамы образуют один комплект ценностью $$$5+9=14$$$.
Во втором примере можно сначала снять пижамы с исходными номерами $$$2$$$ и $$$3$$$, а затем — с исходными номерами $$$1$$$ и $$$4$$$. Суммарная ценность комплектов равна $$$(1+3)+(100+4)=108$$$. На конвейере останутся три красные пижамы.
В третьем примере все пижамы синие, поэтому собрать ни одного комплекта не получится.
November 14 is Good Stone Day in Japan. At the holiday exhibition, Mika carries the stones entered in the contest from one platform to another. After the first downpour, the spectators asked the judges to add figure skating with a stone to the program.
The platforms form two rows of $$$n+1$$$ platforms each. The columns are numbered from $$$0$$$ to $$$n$$$ from left to right. Row $$$0$$$ is the upper row, and row $$$1$$$ is the lower row. Platform $$$(x,y)$$$ is in column $$$x$$$ and row $$$y$$$.
In each column, a vertical walkway connects the two platforms. In each row, a horizontal walkway connects the platforms in each pair of adjacent columns. Each passable walkway can be used in either direction.
Zone $$$i$$$ contains the vertical walkway in column $$$i$$$ and, if $$$i \gt 0$$$, both horizontal walkways between columns $$$i-1$$$ and $$$i$$$. For example, both horizontal walkways between columns $$$0$$$ and $$$1$$$ belong to zone $$$1$$$.
The weather in each zone is either dry or rainy. Each walkway has one of two types. An all-weather walkway is passable in any weather, while a slippery walkway is passable only when its zone is dry.
A path is passable if all its walkways are passable. Its length is the number of walkways traversed. For $$$0 \le x \le y \le n$$$, let $$$P_{x,y}$$$ be the number of passable paths from $$$(x,0)$$$ to $$$(y,1)$$$ of length exactly $$$y-x+1$$$.
Process $$$q$$$ queries in the given order.
$$$$$$A = \sum_{0 \le x \le y \le n} P_{x,y}, \qquad B = \sum_{0 \le x \le y \le n} (y-x+1) P_{x,y}.$$$$$$
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of columns excluding column $$$0$$$ and the number of queries.
The second line contains a binary string $$$w$$$ of length $$$n+1$$$, describing the weather in zones $$$0$$$ through $$$n$$$ in order. The character 0 means dry weather, and 1 means rain.
The third line contains a binary string $$$v$$$ of length $$$n+1$$$, describing the types of the vertical walkways in columns $$$0$$$ through $$$n$$$ in order.
The fourth line contains a binary string $$$u$$$ of length $$$n$$$, describing the types of the upper horizontal walkways in zones $$$1$$$ through $$$n$$$ in order.
The fifth line contains a binary string $$$d$$$ of length $$$n$$$, describing the types of the lower horizontal walkways in zones $$$1$$$ through $$$n$$$ in order.
In the strings $$$v$$$, $$$u$$$, and $$$d$$$, the character 0 denotes an all-weather walkway, and 1 denotes a slippery walkway.
Each of the next $$$q$$$ lines contains one query in one of the following formats.
For each query of type $$$3$$$, output two integers $$$A \bmod 998\,244\,353$$$ and $$$B \bmod 998\,244\,353$$$ on a separate line.
If there are no queries of type $$$3$$$, the output is empty.
1 10000003
4 6
2 5000111110031 1 231 0 13
10 20 3 6 4 8
1 701011132 1 232 1 032 1 13
1 1 2 3 3 4 4 6
2 9111111111132 0 031 0 032 0 031 0 03
0 0 1 1 1 1 1 1 0 0
3 31111011001001031 2 23
4 6 14 35
In the first example, all walkways are passable. There are two paths of length $$$1$$$, one along the vertical walkway in each column, and two paths of length $$$2$$$ from $$$(0,0)$$$ to $$$(1,1)$$$. The two paths reach the lower row in different columns.
In the second example, there are initially three paths of length $$$1$$$, four paths of length $$$2$$$, and three paths of length $$$3$$$. After the first weather switch, a path can reach the lower row only in column $$$0$$$. From there it can reach any of the three lower platforms. After the second weather switch, the only passable vertical walkway is in column $$$1$$$. A path can start in column $$$0$$$ or $$$1$$$ and end in column $$$1$$$ or $$$2$$$. This gives four paths of lengths $$$2$$$, $$$3$$$, $$$1$$$, and $$$2$$$.
In the third example, the vertical walkway in column $$$0$$$ is initially the only passable walkway. The first type switch opens the lower horizontal walkway, adding a path of length $$$2$$$. The second switch opens the vertical walkway in column $$$1$$$, adding a path of length $$$1$$$. The third switch opens the upper horizontal walkway, adding another path of length $$$2$$$.
In the fourth example, all walkways are initially slippery and it is raining in every zone, so there are no paths. After the first query of type $$$2$$$, a path can use the vertical walkway in column $$$0$$$. When the walkway becomes slippery again, its zone is dry, so it can be used until it rains again.
In the fifth example, the only passable vertical walkways are initially in columns $$$0$$$ and $$$3$$$. Each of these columns gives two paths, one of length $$$1$$$ and one of length $$$2$$$. Then the weather in zone $$$2$$$ becomes dry, opening its two horizontal walkways and its vertical walkway. Four paths reach the lower row in column $$$0$$$, six in column $$$2$$$, and four in column $$$3$$$.
14 ноября в США отмечается День американского плюшевого мишки. В честь праздника спортивный клуб Димы решил провести нешуточный турнир по жиму лёжа. Победителю обещали вручить огромного плюшевого медведя, поэтому Дима решил как следует подготовиться.
У Димы есть план тренировки, согласно которому он должен выполнить $$$n$$$ подходов. В $$$i$$$-м подходе ему необходимо поднять штангу общим весом $$$a_i$$$ килограммов. Вес пустой штанги равен $$$C$$$ килограммам.
В зале есть блины следующих весов:
Количество блинов каждого веса не ограничено.
Таким образом, для $$$i$$$-го подхода на каждую сторону штанги необходимо повесить блины суммарным весом $$$(a_i-C)/2$$$ килограмма. Наборы блинов на двух сторонах должны быть одинаковыми. На каждой стороне блины расположены по невозрастанию веса от центра штанги к её краю: более тяжёлые блины находятся ближе к грифу.
Для каждого подхода Дима обязан использовать набор с минимально возможным количеством блинов, позволяющий получить требуемый вес. Если существует несколько таких наборов, Дима может выбрать любой из них.
Изначально штанга пустая. Между подходами Дима может снимать и надевать блины только с внешнего края каждой стороны штанги. Снятие одного физического блина и надевание одного физического блина считаются отдельными операциями. Первоначальная установка блинов перед первым подходом также учитывается.
Дима хочет минимизировать суммарное количество операций снятия и надевания блинов за всю тренировку. Помогите ему найти это количество или определить, что выполнить план невозможно.
В первой строке записаны целое число $$$n$$$ и число $$$C$$$ ($$$1 \le n \le 200000$$$, $$$0 \le C \le 10^9$$$) — количество подходов и вес пустой штанги.
Во второй строке записаны $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — требуемые общие веса штанги в соответствующих подходах.
Каждое из чисел $$$C$$$, $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ является целым или полуцелым, то есть имеет не более одного знака после десятичной точки, причём после точки может стоять только цифра $$$5$$$.
Выведите минимальное суммарное количество операций снятия и надевания физических блинов. Если хотя бы один подход невозможно выполнить, выведите $$$-1$$$.
3 2080 90 80
12
3 2022.5 23 25
-1
3 20.523 25.5 23
10
Для веса 80 кг на штанге весом 20 кг на каждой стороне должна быть масса блинов 30 кг. Можно использовать, например, блины 15 кг и 15 кг либо 20 кг и 10 кг. Во втором случае блины расположены в порядке 20, 10 от центра к краю.
Для последовательности из примера можно использовать конфигурации 20, 10, затем 20, 15, и затем снова 20, 10 на каждой стороне. Сначала Дима надевает четыре блина. Между первым и вторым подходами он снимает два блина по 10 кг и надевает два блина по 15 кг. Между вторым и третьим подходами он выполняет обратную замену. Всего получается 4 + 4 + 4 = 12 операций.
14 ноября в Сайтаме отмечают День префектуры. Префектура в Японии — примерно то же, что область в России.
К празднику в городском парке устроили квест. По всему парку спрятали подсказки, а на финише поставили сундук с призами. На крышке сундука — экран с девятью точками. Точки образуют квадратную сетку $$$3 \times 3$$$ и пронумерованы следующим образом:
7 8 9
4 5 6
1 2 3
Для того чтобы открыть сундук, требуется графический ключ, который задаётся последовательностью цифр. Экран соединяет отрезком точки, соответствующие каждой паре соседних цифр. Отрезки могут пересекаться и накладываться друг на друга. Если в ключе одна цифра, на экране появляется одна точка.
Два графических ключа считаются одинаковыми, если при наложении их рисунков на одной и той же сетке каждый из них целиком закрывает другой.
Денис и его команда собрали подсказки и составили графический ключ. У организаторов записан правильный ключ. Сундук откроется, если ключ Дениса совпадёт с правильным. Определите, откроется ли сундук.
В первой строке записан правильный графический ключ.
Во второй строке записан графический ключ Дениса.
Каждый ключ представляет собой непустую строку из цифр от $$$1$$$ до $$$9$$$. Внутри каждого ключа все цифры различны.
Выведите YES, если сундук откроется, и NO в противном случае.
4178871
YES
168186
NO
Первый пример (слева) и второй пример (справа) 14 ноября в США отмечают День ремня безопасности. К празднику Денис и его команда решили устроить пробную поездку беспилотного такси. Первого пассажира, испытательного манекена, посадили на заднее сиденье и пристегнули ремнём. Теперь такси должно отвезти его к заданной остановке.
Испытательный полигон моделируется бесконечным клетчатым полем. Стартовая клетка и клетка остановки заданы целочисленными координатами. Каждая команда перемещает такси на одну клетку вверх, вниз, влево или вправо.
Денис может загрузить в такси программу из ровно $$$X$$$ команд. После последней команды такси снова выполняет первую и продолжает движение с текущей клетки. Программа повторяется бесконечно.
Определите, может ли Денис составить программу, с которой такси хотя бы раз окажется в клетке остановки. Если такси уже стоит в этой клетке, пассажир находится на месте ещё до выполнения первой команды.
В первой строке записано целое число $$$X$$$ ($$$1 \le X \le 2 \cdot 10^5$$$) — число команд в программе.
Во второй строке записаны два целых числа $$$x_s$$$ и $$$y_s$$$ — координаты стартовой клетки. В третьей строке записаны два целых числа $$$x_t$$$ и $$$y_t$$$ — координаты клетки остановки.
Все координаты лежат в диапазоне от $$$-10^{12}$$$ до $$$10^{12}$$$ включительно.
Выведите YES, если Денис может составить программу, с которой такси хотя бы раз окажется в клетке остановки. В противном случае выведите NO.
30 03 1
YES
20 03 1
NO
1-5 7-5 7
YES
В первом примере подходит программа «вправо, вправо, вверх». После первого выполнения программы такси находится в клетке $$$(2, 1)$$$. Следующая команда «вправо» приводит его к остановке в клетке $$$(3, 1)$$$.
Во втором примере команды вдоль одной оси не подходят, поскольку у остановки обе координаты отличаются от стартовых. Чтобы увеличить обе координаты, нужны команды «вправо» и «вверх». На рисунке показаны оба возможных порядка этих команд. В обоих случаях такси покидает строку $$$y = 1$$$ раньше, чем достигает $$$x = 3$$$.
В третьем примере такси находится в клетке остановки ещё до выполнения первой команды.
14 ноября в России отмечается День дизайнера упаковки. В этот день на фабрику привезли $$$n$$$ коробок, выстроенных в ряд. Дизайн каждой коробки обозначен целым числом от $$$1$$$ до $$$k$$$. Дизайн $$$i$$$-й коробки обозначим как $$$a_i$$$. Также задана таблица $$$f$$$ размера $$$k \times k$$$ со значениями дизайнов. Пока есть хотя бы две коробки, можно взять две соседние с дизайнами $$$u$$$ и $$$v$$$ и упаковать их в одну коробку с дизайном $$$f_{u,v}$$$. При этой операции число коробок уменьшается на $$$1$$$. Обратите внимание, что порядок коробок важен: $$$f_{u,v}$$$ может отличаться от $$$f_{v,u}$$$.
Более формально, пусть текущий массив имеет вид $$$b_1, b_2, \ldots, b_m$$$. За одну операцию можно выбрать индекс $$$i$$$ ($$$1 \le i \lt m$$$), удалить элементы $$$b_i$$$ и $$$b_{i+1}$$$ и поставить на их место элемент $$$f_{b_i, b_{i+1}}$$$. После этого длина массива уменьшается на $$$1$$$.
Вам нужно ответить на несколько независимых запросов. Каждый запрос представляет собой три числа: $$$l, r, x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le k$$$). Вам нужно ответить, можно ли, применяя операцию упаковки к подотрезку $$$a_l, a_{l+1}, \ldots, a_r$$$, упаковать все коробки в одну с дизайном $$$x$$$. Обратите внимание, что запросы независимы: операции не изменяют исходный ряд коробок между запросами.
В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 400$$$, $$$1 \le k \le 10$$$) — количество коробок и количество возможных дизайнов.
Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le k$$$) — изначальные дизайны коробок.
Следующие $$$k$$$ строк описывают таблицу $$$f$$$. В $$$i$$$-й из этих строк ($$$1 \le i \le k$$$) заданы $$$k$$$ целых чисел $$$f_{i,1}, f_{i,2}, \ldots, f_{i,k}$$$ ($$$1 \le f_{i,j} \le k$$$).
В следующей строке задано одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.
В каждой из следующих $$$q$$$ строк заданы три целых числа $$$l$$$, $$$r$$$ и $$$x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le k$$$) — границы подотрезка и целевой дизайн коробки.
Для каждого запроса выведите на отдельной строке «YES», если коробки на отрезке с $$$l$$$-й по $$$r$$$-ю можно упаковать в одну коробку с дизайном $$$x$$$, и «NO» в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
3 31 2 31 1 23 2 12 3 331 3 11 3 21 3 3
YES YES NO
4 42 4 1 33 4 1 21 2 4 34 1 3 22 3 1 442 4 41 4 22 3 11 2 3
YES YES NO YES
В первом наборе входных данных массив коробок имеет вид $$$[1, 2, 3]$$$.
Рассмотрим все возможные способы упаковать этот отрезок в одну коробку:
Ежегодно 14 ноября отмечается Международный день скептиков — праздник критического мышления, сомнений в очевидном и научной проверки любых утверждений.
К этому дню в музее занимательной науки иллюзионист подготовил оптический аттракцион, утверждая, что сложная система зеркал способна создавать принципиально новые и непостижимые иллюзии. В лабиринте аттракциона на плоскости установлена последовательность из $$$n$$$ оптических зеркал, которые луч лазера проходит строго по порядку:
Учёный-скептик, пришедший на выставку, сразу заподозрил фокусника в избыточном усложнении конструкции. Скептик утверждает, что многие зеркала установлены лишь для создания ложной видимости сложности. Чтобы доказать это на практике, он хочет убрать ровно один непустой непрерывный фрагмент подряд идущих зеркал с номерами от $$$l$$$ до $$$r$$$ ($$$1 \le l \le r \le n$$$) так, чтобы для любой начальной точки лазерного луча $$$(x, y)$$$ его итоговое положение после прохождения оставшихся зеркал (в прежнем порядке) осталось в точности таким же, как и при прохождении всех $$$n$$$ зеркал.
Помогите скептику разоблачить иллюзиониста: посчитайте количество таких непустых непрерывных фрагментов $$$[l, r]$$$, удаление которых никак не влияет на итоговое оптическое преобразование плоскости.
В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество зеркальных преобразований.
В следующих $$$n$$$ строках описаны операции в порядке их выполнения. Каждая строка имеет один из трёх видов:
Выведите одно целое число — количество непустых непрерывных фрагментов операций, удаление которых сохраняет итоговое преобразование для любой начальной точки.
4V 2H -1V 2H -1
1
4DV 5DH 5
1
5V 3V 3V 3DD
4
В первом примере вертикальное отражение относительно $$$x = 2$$$ и горизонтальное отражение относительно $$$y = -1$$$ независимы по координатам и коммутируют, поэтому применение всех четырёх операций возвращает любую точку $$$(x, y)$$$ на исходное место: $$$(T_4 = T_0)$$$. Скептик может убрать весь фрагмент $$$[1, 4]$$$ целиком — удаление любого другого подотрезка изменит итоговое положение луча.
Во втором примере иллюзионист попытался замаскировать горизонтальное отражение H 5 с помощью диагональных зеркал: $$$$$$(x, y) \xrightarrow{\t{D}} (y, x) \xrightarrow{\t{V 5}} (10 - y, x) \xrightarrow{\t{D}} (x, 10 - y).$$$$$$ Композиция первых трёх зеркал в точности эквивалентна H 5. Вместе с четвёртым зеркалом H 5 они взаимно уничтожаются, поэтому удаление всего фрагмента $$$[1, 4]$$$ сохраняет итоговое преобразование.
В третьем примере подходящими являются $$$4$$$ фрагмента: $$$[1, 2]$$$, $$$[2, 3]$$$, $$$[4, 5]$$$ и $$$[2, 5]$$$. Например, удаление фрагмента $$$[1, 2]$$$ оставляет зеркала $$$3, 4, 5$$$ (V 3, D, D), что даёт то же итоговое отображение V 3, что и исходная последовательность из пяти зеркал.
14 ноября в США отмечается День маринованного огурца.
Вы приехали в город, где каждый год устраивают ярмарку в честь этого прекрасного праздника. Там вы решили поучаствовать в соревновании по опустошению банок с огурцами.
Перед вами на столе стоят $$$n$$$ банок. В $$$i$$$-й банке изначально лежит $$$a_i$$$ огурцов.
За один ход вы выбираете одну непустую банку и вынимаете из неё от одного до всех оставшихся в ней огурцов. Жюри начисляет по одному штрафному баллу за каждый огурец, вынутый на этом ходу, и по одному за каждый огурец во всех остальных банках.
Пустые банки сразу убирают со стола. Соревнование заканчивается, когда на столе не остаётся банок. Какое минимальное суммарное количество штрафных баллов вы можете набрать?
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество банок.
Во второй строке даны $$$n$$$ целых чисел $$$a_1,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — начальное количество огурцов в каждой банке.
Выведите одно целое число — минимальное суммарное количество штрафных баллов.
43 1 4 2
20
17
7
32 2 2
12
В первом примере можно опустошить третью банку, затем первую, четвёртую и вторую. Штрафы за эти ходы равны соответственно $$$10$$$, $$$6$$$, $$$3$$$ и $$$1$$$.
Если на первом ходу вынуть один огурец из банки с четырьмя, штраф составит $$$1 + (3 + 1 + 2) = 7$$$ баллов. Первое слагаемое соответствует вынутому огурцу, а сумма в скобках — огурцам в остальных банках.
Во втором примере можно опустошить единственную банку за один ход и получить $$$7$$$ баллов. В третьем примере можно опустошать банки целиком в любом порядке, получая $$$6$$$, $$$4$$$ и $$$2$$$ балла.
14 ноября 2026 года в Нидерландах отмечается прибытие Синтерклааса, который по традиции привозит детям подарки.
Помощники Синтерклааса отправились на автомобиле развозить подарки. Первую половину пути они проехали с постоянной скоростью $$$x$$$ километров в час, а вторую половину пути с постоянной скоростью $$$y$$$ километров в час. Остановок во время поездки не было.
Найдите среднюю скорость автомобиля за всю поездку.
Средняя скорость равна отношению длины всего пути ко времени, затраченному на его прохождение.
В единственной строке заданы два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le 10^9$$$) — скорости автомобиля помощников Синтерклааса на первой и второй половинах пути в километрах в час.
Выведите одно вещественное число — среднюю скорость автомобиля с подарками за всю поездку в километрах в час.
Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит $$$10^{-4}$$$.
Формально, если ваш ответ равен $$$a$$$, а правильный ответ равен $$$b$$$, то должно выполняться
$$$$$$ \frac{|a-b|}{\max(1,|b|)} \le 10^{-4}. $$$$$$
60 40
48.000000000000
90 90
90.000000000000
1 2
1.333333333333
В первом примере можно считать, что помощникам Синтерклааса необходимо проехать $$$120$$$ километров, чтобы развезти подарки. Первые $$$60$$$ километров автомобиль проехал за $$$1$$$ час, а оставшиеся $$$60$$$ километров — за $$$1{,}5$$$ часа. Средняя скорость равна $$$120 / (1 + 1{,}5) = 48$$$ километрам в час.
Во втором примере помощники Синтерклааса ехали с одинаковой скоростью на обеих половинах пути, поэтому средняя скорость равна $$$90$$$ километрам в час.
В третьем примере для маршрута длиной $$$2$$$ километра время поездки равно $$$1 + 1/2 = 1{,}5$$$ часа. Средняя скорость автомобиля с подарками равна $$$2 / 1{,}5 = 4/3$$$ километра в час.
Ежегодно 14 ноября в Швеции отмечается День шведского чизкейка (Ostkakans dag) — праздник традиционной творожной запеканки из провинции Смоланд, которую подают тёплой с морошковым джемом и взбитыми сливками.
По случаю праздника на длинной дегустационной витрине в ряд выставили $$$n$$$ одинаковых коробочек, пронумерованных слева направо от $$$1$$$ до $$$n$$$. В одну из коробочек шеф-кондитер положил особую порцию золотистой усткаки со счастливым цельным миндалём, однако никто из гостей не знает, в какой именно коробочке она находится — изначально она может быть в любой из $$$n$$$ позиций.
Чтобы подогреть азарт перед дегустацией, кондитер запускает механическую ленту витрины, которая последовательно выполняет строку $$$s$$$ из $$$m$$$ команд L и R:
Определите, на скольких различных конечных позициях витрины может оказаться коробочка со счастливым шведским чизкейком после выполнения всех $$$m$$$ команд.
В первой строке даны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — количество позиций на дегустационной витрине и количество команд соответственно.
Во второй строке дана строка $$$s$$$ длины $$$m$$$, состоящая только из заглавных латинских букв L и R.
Выведите одно целое число — количество различных позиций витрины, на которых может оказаться счастливый шведский чизкейк после выполнения всех $$$m$$$ команд.
5 3LLR
3
3 5LLLLL
1
10 4RLRL
9
В первом примере на витрине $$$n = 5$$$ позиций, а последовательность команд равна LLR. Проследим за множеством возможных позиций коробочки со счастливым чизкейком после каждого сдвига:
Во втором примере после $$$5$$$ сдвигов влево с любой стартовой позиции от $$$1$$$ до $$$3$$$ коробочка упрётся в левый бортик витрины и гарантированно окажется на позиции $$$1$$$.