Как всем известно, 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$$$, любой из них будет засчитан.
14 ноября в Японии отмечается День соуса тартар. На фестивале жареных устриц у Аки попросили ещё немного соуса. Аки восприняла просьбу всерьёз и проложила между прилавками трубы.
Всего есть $$$n$$$ прилавков, пронумерованных от $$$1$$$ до $$$n$$$ по часовой стрелке. Для $$$1 \le i \lt n$$$ труба $$$i$$$ соединяет прилавки $$$i$$$ и $$$i+1$$$. Труба $$$n$$$ соединяет прилавки $$$n$$$ и $$$1$$$.
Для прилавка $$$i$$$ задано целое число $$$a_i$$$. Если $$$a_i \gt 0$$$, в прилавок извне поступает $$$a_i$$$ литров соуса в секунду. Если $$$a_i \lt 0$$$, из прилавка забирают $$$-a_i$$$ литров соуса в секунду. Например, при $$$a_i = -3$$$ из прилавка забирают три литра в секунду. Если $$$a_i = 0$$$, внешней подачи и забора нет.
Для каждой трубы можно бесплатно выбрать направление потока и постоянный неотрицательный целый расход в литрах в секунду. Расход может быть нулевым. Пропускная способность трубы $$$i$$$ равна $$$b_i$$$ литрам в секунду в любом из двух направлений. За $$$c_i$$$ денежных единиц трубу $$$i$$$ можно заменить трубой с неограниченной пропускной способностью.
В каждом прилавке суммарный приток соуса должен равняться суммарному оттоку. При этом учитываются как потоки по трубам, так и внешняя подача и забор. Найдите минимальную суммарную стоимость замены труб, при которой можно выполнить это требование.
Первая строка содержит целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество прилавков.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). Гарантируется, что $$$a_1 + a_2 + \cdots + a_n = 0$$$.
Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — пропускные способности труб.
Четвёртая строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — стоимости замены труб.
Выведите одно целое число — минимальную суммарную стоимость замены труб.
Можно показать, что допустимая настройка потоков всегда существует, если заменить все трубы.
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
В первом примере заменять трубы не нужно. По трубе $$$1$$$ можно направить два литра в секунду от прилавка $$$1$$$ к прилавку $$$2$$$. По трубе $$$3$$$ можно направить один литр в секунду от прилавка $$$4$$$ к прилавку $$$3$$$, а по трубе $$$4$$$ — два литра в секунду от прилавка $$$1$$$ к прилавку $$$4$$$. По трубе $$$2$$$ соус не течёт.
Во втором примере, если оставить любые две трубы без замены, у общего для них прилавка не будет потока по трубам, хотя $$$a_i$$$ для него отлично от нуля. Можно оставить трубу $$$2$$$, направив два литра в секунду от прилавка $$$1$$$ к прилавку $$$2$$$ и один литр в секунду от прилавка $$$1$$$ к прилавку $$$3$$$. Это стоит $$$2 + 4 = 6$$$.
В третьем примере нужно доставить четыре литра в секунду от прилавка $$$3$$$ к прилавку $$$5$$$. Для маршрута по часовой стрелке нужно заменить трубы $$$3$$$ и $$$4$$$ за $$$15$$$ денежных единиц. Для маршрута против часовой стрелки нужно заменить трубы $$$2$$$, $$$1$$$ и $$$5$$$ за $$$6$$$ денежных единиц. Второй маршрут обходится дешевле.
В четвёртом примере во всех трубах можно установить нулевой расход.
В пятом примере прилавку $$$3$$$ нужно получать два литра в секунду от прилавка $$$1$$$. По маршруту через прилавок $$$2$$$ без замены труб можно передать не больше одного литра в секунду, а по маршруту через прилавок $$$4$$$ соус без замены труб пройти не может. Замена одной трубы на маршруте не увеличивает его пропускную способность. Замена обеих труб на любом из этих маршрутов стоит $$$9$$$ денежных единиц и позволяет передать нужный объём.
В шестом примере любые две трубы с нулевым расходом отсекают от остальных непустую часть кольца, в которой сумма $$$a_i$$$ отлична от нуля. Поэтому можно оставить не более одной трубы. Например, если оставить трубу $$$4$$$, по трубам $$$1$$$ и $$$2$$$ можно направить по часовой стрелке $$$10^9$$$ и $$$10^9-1$$$ литров в секунду соответственно, а по трубе $$$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$$$. На конвейере останутся три красные пижамы.
В третьем примере все пижамы синие, поэтому собрать ни одного комплекта не получится.
14 ноября в Японии отмечается День хорошего камня. На праздничной выставке смотритель Мика разносит конкурсные камни по площадкам. После первого ливня зрители предложили жюри добавить в программу фигурное катание с камнем.
Площадки образуют два ряда по $$$n+1$$$ площадке. Столбцы пронумерованы слева направо от $$$0$$$ до $$$n$$$. Верхний ряд имеет номер $$$0$$$, нижний — номер $$$1$$$. Площадка $$$(x,y)$$$ находится в столбце $$$x$$$ и ряду $$$y$$$.
В каждом столбце две площадки соединены вертикальной дорожкой. В каждом ряду площадки соседних столбцов соединены горизонтальной дорожкой. По любой проходимой дорожке можно идти в обе стороны.
Зона $$$i$$$ включает вертикальную дорожку в столбце $$$i$$$ и, если $$$i \gt 0$$$, обе горизонтальные дорожки между столбцами $$$i-1$$$ и $$$i$$$. Например, обе горизонтальные дорожки между столбцами $$$0$$$ и $$$1$$$ относятся к зоне $$$1$$$.
В каждой зоне либо сухо, либо идёт дождь. Каждая дорожка бывает одного из двух типов. Всепогодная дорожка проходима при любой погоде, а скользкая — только если в её зоне сухо.
Путь проходим, если проходимы все его дорожки. Длина пути равна числу пройденных дорожек. Для $$$0 \le x \le y \le n$$$ обозначим через $$$P_{x,y}$$$ число проходимых путей из $$$(x,0)$$$ в $$$(y,1)$$$ длины ровно $$$y-x+1$$$.
Обработайте $$$q$$$ запросов в заданном порядке.
$$$$$$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}.$$$$$$
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — число столбцов без учёта столбца $$$0$$$ и число запросов.
Вторая строка содержит двоичную строку $$$w$$$ длины $$$n+1$$$, описывающую погоду в зонах от $$$0$$$ до $$$n$$$ по порядку. Символ 0 означает сухую погоду, а 1 — дождь.
Третья строка содержит двоичную строку $$$v$$$ длины $$$n+1$$$, описывающую типы вертикальных дорожек в столбцах от $$$0$$$ до $$$n$$$ по порядку.
Четвёртая строка содержит двоичную строку $$$u$$$ длины $$$n$$$, описывающую типы верхних горизонтальных дорожек в зонах от $$$1$$$ до $$$n$$$ по порядку.
Пятая строка содержит двоичную строку $$$d$$$ длины $$$n$$$, описывающую типы нижних горизонтальных дорожек в зонах от $$$1$$$ до $$$n$$$ по порядку.
В строках $$$v$$$, $$$u$$$ и $$$d$$$ символ 0 обозначает всепогодную дорожку, а 1 — скользкую.
Каждая из следующих $$$q$$$ строк содержит один запрос в одном из трёх форматов.
Для каждого запроса типа $$$3$$$ выведите в отдельной строке два целых числа $$$A \bmod 998\,244\,353$$$ и $$$B \bmod 998\,244\,353$$$.
Если запросов типа $$$3$$$ нет, вывод должен быть пустым.
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
В первом примере все дорожки проходимы. Есть два пути длины $$$1$$$, по вертикальной дорожке в каждом столбце, и два пути длины $$$2$$$ из $$$(0,0)$$$ в $$$(1,1)$$$. Эти два пути отличаются столбцом, в котором переходят в нижний ряд.
Во втором примере изначально есть три пути длины $$$1$$$, четыре пути длины $$$2$$$ и три пути длины $$$3$$$. После первого изменения погоды перейти в нижний ряд можно только в столбце $$$0$$$. Из него можно дойти до любой из трёх нижних площадок. После второго изменения погоды вертикальная дорожка проходима только в столбце $$$1$$$. До неё можно добраться из столбца $$$0$$$ или $$$1$$$, а после неё можно закончить путь в столбце $$$1$$$ или $$$2$$$. Получаются четыре пути длины $$$2$$$, $$$3$$$, $$$1$$$ и $$$2$$$.
В третьем примере сначала проходима только вертикальная дорожка в столбце $$$0$$$. Первое изменение типа открывает нижнюю горизонтальную дорожку и добавляет путь длины $$$2$$$. Второе изменение открывает вертикальную дорожку в столбце $$$1$$$ и добавляет путь длины $$$1$$$. Третье изменение открывает верхнюю горизонтальную дорожку и добавляет ещё один путь длины $$$2$$$.
В четвёртом примере изначально все дорожки скользкие и во всех зонах идёт дождь, поэтому путей нет. После первого запроса типа $$$2$$$ появляется путь по вертикальной дорожке в столбце $$$0$$$. Когда эта дорожка снова становится скользкой, в её зоне сухо, поэтому по ней можно пройти до следующего дождя.
В пятом примере сначала пройти по вертикальной дорожке можно только в столбцах $$$0$$$ и $$$3$$$. Каждый из них даёт по два пути длины $$$1$$$ и $$$2$$$. Затем в зоне $$$2$$$ становится сухо. Открываются обе её горизонтальные дорожки и вертикальная дорожка. Четыре пути переходят в нижний ряд в столбце $$$0$$$, шесть — в столбце $$$2$$$, ещё четыре — в столбце $$$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$$$.