Монокарп решил купить игрушки на новогоднюю елку. В магазине есть игрушки трех цветов — красные, желтые и синие. Известно, что в магазине есть неограниченное количество игрушек каждого цвета.
Одна игрушка красного цвета стоит $$$r$$$ бурлей, одна игрушка желтого цвета стоит $$$y$$$ бурлей, а одна игрушка синего цвета стоит $$$b$$$ бурлей.
У Монокарпа есть всего $$$n$$$ бурлей, и он хочет купить как можно больше игрушек. При этом он считает, что елка будет красиво украшена, если количества игрушек каждого цвета, которые он купит, отличаются друг от друга не более, чем на единицу. Более формально, если Монокарп купит $$$cnt_r$$$ игрушек красного цвета, $$$cnt_y$$$ игрушек желтого цвета и $$$cnt_b$$$ игрушек синего цвета, то должны выполняться неравенства: $$$|cnt_r - cnt_y| \le 1$$$, $$$|cnt_r - cnt_b| \le 1$$$, $$$|cnt_y - cnt_b| \le 1$$$.
Определите максимальное суммарное количество игрушек, которые Монокарп может купить в магазине, при условии, что количества купленных игрушек каждого цвета должны отличаться не более, чем на единицу.
В первой строке задано целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество бурлей, которое есть у Монокарпа.
Во второй строке задано целое число $$$r$$$ ($$$1 \le r \le n$$$) — стоимость в бурлях одной игрушки красного цвета.
В третьей строке задано целое число $$$y$$$ ($$$1 \le y \le n$$$) — стоимость в бурлях одной игрушки желтого цвета.
В четвертой строке задано целое число $$$b$$$ ($$$1 \le b \le n$$$) — стоимость в бурлях одной игрушки синего цвета.
Выведите максимальное суммарное количество игрушек, которые Монокарп может купить в магазине, при условии, что количества купленных игрушек каждого цвета должны отличаться не более, чем на единицу.
12 2 2 2
6
26 1 4 7
7
17 4 2 3
5
100 100 100 100
1
В первом примере Монокарп может купить по две игрушки каждого цвета, потратив на это все $$$12$$$ бурлей, которые у него есть. Таким образом, максимально Монокарп может купить $$$6$$$ игрушек.
Во втором примере Монокарп может купить $$$3$$$ игрушки красного цвета, $$$2$$$ игрушки желтого цвета и $$$2$$$ игрушки синего цвета, потратив на это $$$3 \cdot 1 + 2 \cdot 4 + 2 \cdot 7 = 25$$$ бурлей. Таким образом, максимально Монокарп может купить $$$7$$$ игрушек. При этом у Монокарпа останется $$$1$$$ бурль, но купить еще одну игрушку красного цвета он не может, так как в этом случае нарушится ограничение на количества купленных игрушек, описанное в условии.
В третьем примере Монокарп может купить $$$1$$$ игрушку красного цвета, $$$2$$$ игрушки желтого цвета и $$$2$$$ игрушки синего цвета, потратив на это $$$1 \cdot 4 + 2 \cdot 2 + 2 \cdot 3 = 14$$$ бурлей. Таким образом, максимально Монокарп может купить $$$5$$$ игрушек.
В шеренге плечом к плечу слева направо стоят $$$n$$$ солдат. Голова каждого солдата повернута либо влево, либо вправо, то есть каждый из солдат смотрит либо строго влево, либо строго вправо.
Вам нужно дать некоторым солдатам команду развернуть головы в противоположном направлении, то есть после выполнения этой команды солдат, смотревший влево, должен развернуть голову вправо, а солдат, смотревший вправо, должен развернуть голову влево. После выполнения команды должен существовать солдат, в сторону которого смотрят все остальные солдаты (в какую сторону он смотрит, не имеет значения). Поворачивают голову только те солдаты, которым была отдана команда.
Например, если в шеренге стоят $$$5$$$ солдат, и первые три солдата смотрят вправо, а пятый солдат смотрит влево, то все они смотрят в сторону четвертого солдата.
Определите минимальное количество солдат, которым нужно дать команду развернуть голову, чтобы все солдаты смотрели в сторону какого-то одного солдата.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 2\,000$$$) — количество солдат в шеренге.
Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая из букв «L» и «R». Если $$$i$$$-й символ строки равен «L», то $$$i$$$-й солдат смотрит влево. Если $$$i$$$-й символ строки равен «R», то $$$i$$$-й солдат смотрит вправо.
Выведите минимальное количество солдат, которым нужно дать команду развернуть голову, чтобы существовал солдат, в сторону которого смотрят все остальные солдаты (в какую сторону он смотрит, не имеет значения).
6 LRRRLR
2
3 LLL
0
10 LLRRLRRRRL
3
В первом примере нужно дать команду повернуть головы, например, первому и шестому солдатам. После этого шеренга будет выглядеть «RRRRLL». Таким образом, все, кроме пятого солдата, будут смотреть на пятого солдата.
Во втором примере все солдаты смотрят влево, то есть второй и третий солдаты смотрят на первого солдата, поэтому отдавать команду повернуть голову не нужно никому.
Недавно в городе, где живет Монокарп, построили дом с новой планировкой. Согласно данной планировке в доме есть три типа квартир: трехкомнатные, пятикомнатные и семикомнатные. Известно, что в каждой комнате есть ровно по одному окну. Таким образом, в трехкомнатной квартире три окна, в пятикомнатной — пять, в семикомнатной — семь.
Монокарп обошел дом со всех сторон и насчитал в нем $$$n$$$ окон. Монокарпу стало интересно, сколько квартир каждого типа может быть в этом доме.
К сожалению, Монокарп только научился считать, поэтому попросил вас помочь ему найти возможное количество трехкомнатных, пятикомнатных и семикомнатных квартир в доме, если известно, что во всех квартирах этого дома ровно $$$n$$$ окон. Так как ответов может быть несколько, разрешается вывести любой подходящий.
В первой строке задано целое число $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — количество окон в доме.
Если дома с новой планировкой и заданным количеством окном просто не может быть, выведите $$$-1$$$.
В противном случае, выведите три целых неотрицательных числа — количество трехкомнатных, пятикомнатных и семикомнатных квартир в доме. Если подходящих ответов несколько, выведите любой из них.
30
2 2 2
67
7 5 3
4
-1
В первом примере один из возможных ответов — $$$2$$$ трехкомнатные квартиры, $$$2$$$ пятикомнатные квартиры и $$$2$$$ семикомнатные квартиры. Таким образом, количество окон в квартирах равно $$$2 \cdot 3 + 2 \cdot 5 + 2 \cdot 7 = 30$$$.
Перед вами в ряд выстроены $$$n$$$ бочек, пронумерованные слева направо, начиная с единицы. В $$$i$$$-й бочке налито $$$a_i$$$ литров воды.
Вы можете переливать воду из одной бочки в другую. В ходе одного переливания вы можете выбрать две разные бочки с номерами $$$x$$$ и $$$y$$$ (бочка $$$x$$$ должна быть непустой) и перелить любое возможное количество воды из бочки $$$x$$$ в бочку $$$y$$$ (возможно, всю воду). Считайте, что каждая бочка имеет бесконечную емкость, то есть в бочку можно налить сколько угодно воды.
Определите максимальную разность между бочкой с наибольшим количество воды и бочкой с наименьшим количеством воды, если вы можете сделать не более $$$k$$$ переливаний.
В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \lt n \le 2 \cdot 10^5$$$) — количество бочек и максимальное количество переливаний, которые вы можете произвести.
Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно изначальному количеству литров воды, которое находится в бочке номер $$$i$$$.
Выведите максимальную разность между бочкой с наибольшим количество воды и бочкой с наименьшим количеством воды, если вы можете сделать не более $$$k$$$ переливаний.
4 1 5 5 5 5
10
3 2 0 0 0
0
В первом примере можно, например, перелить всю воду из второй бочки в четвертую. Тогда количество воды в бочках будет равно $$$[5, 0, 5, 10]$$$, и разность между бочками с максимальным и минимальным количеством воды будет равна $$$10$$$.
Во втором примере ни в одной бочке нет воды, поэтому мы не можем сделать ни одного переливания. Разность между бочками с максимальным и минимальным количеством воды будет равна $$$0$$$.
На доске записаны целые числа $$$1, 2, 3, \dots n$$$ (то есть все целые числа от $$$1$$$ до $$$n$$$ по одному разу). Вы можете за одну операцию стереть с доски два любых числа $$$a$$$ и $$$b$$$ и вместо них записать новое число, равное $$$\frac{a + b}{2}$$$ округленному вверх.
Вы должны выполнить ровно $$$n - 1$$$ описанную операцию, при этом число, которое будет записано на доске в ходе последней операции, должно быть минимально возможным.
Легко показать, что после $$$n - 1$$$ операции на доске будет записано всего одно число, его и нужно минимизировать.
В первой строке задано целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество целых чисел, изначально записанных на доске.
В первую строку выведите минимальное число, которое может остаться на доске после $$$n - 1$$$ операции. В каждой из следующих $$$n - 1$$$ строк выведите по два целых числа — числа $$$a$$$ и $$$b$$$, которые должны быть стерты с доски во время очередной операции.
4
2 2 4 3 3 3 1
В первом примере изначально на доске записаны числа $$$[1, 2, 3, 4]$$$. В ходе первой операции с доски будут стерты числа $$$2$$$ и $$$4$$$, а вместо них будет записано число $$$3$$$. Таким образом, после первой операции на доске будут записаны числа $$$[1, 3, 3]$$$. После второй операции на доске будут записаны числа $$$[1, 3]$$$. После третьей операции на доске останется единственное число $$$2$$$.
Монокарп накопил $$$n$$$ бурлей, пришел в банк и открыл счет, положив на него все $$$n$$$ бурлей.
Так как Монокарп не любит читать лицензионные соглашения, то оказалось, что ему доступны только два вида операций, которые (к счастью) он может совершать неограниченное количество раз:
Считайте, что после того, как Монокарп изначально положил $$$n$$$ бурлей в банк, у него больше нет денег на руках, и у него больше не будет никаких денежных поступлений извне, то есть все операции он совершает именно с теми деньгами, которые положил в банк.
Перед вами стоит задача определить максимальное количество бурлей, которые могут оказаться на руках у Монокарпа, если он может выполнять только описанные операции.
В первой строке заданы три целых числа $$$n$$$, $$$a$$$, $$$b$$$ ($$$1 \le a, b \le n \le 10^{6}$$$) — количество бурлей, которое Монокарп положил на счет в банк, количество бурлей, которые можно взять из банка за одну операцию, и количество бурлей, которые можно положить на счет в банк за одну операцию.
Выведите максимальное количество бурлей, которые могут оказаться на руках у Монокарпа, если он может выполнять только описанные в условии операции.
17 5 3
17
97 10 6
96
77141 21540 3108
77136
Монокарп открыл свою автомобильную парковку. Всего на парковке есть $$$n$$$ мест, расположенных слева направо. Монокарп решил пронумеровать все места своей парковки, но так как он очень не любит цифру $$$k$$$, то нумерация должна получиться своеобразной.
Монокарп будет нумеровать места парковки по очереди (начиная с самого левого) целыми числами, начиная с единицы. Если очередное число, которым Монокарп хочет занумеровать текущее место парковки, содержит в своей записи цифру $$$k$$$, то Монокарп пропустит это число, и будет переходить к следующему числу до тех пор, пока не найдет число, запись которого не содержит цифру $$$k$$$. Именно таким числом Монокарп и занумерует текущее место парковки и перейдет к следующему месту.
Например, если Монокарп не любит цифру $$$1$$$ и на его парковке $$$12$$$ мест, то они будут пронумерованы следующим образом: $$$[2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24]$$$.
Перед вами стоит задача определить номер, который Монокарп присвоит последнему (то есть $$$n$$$-му) месту своей парковки.
В первой строке следуют два целых числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 10^{9}, 0 \le k \le 9)$$$ — количество мест на парковке и цифра, которую не любит Монокарп.
Выведите номер, который Монокарп присвоит $$$n$$$-му парковочному месту.
12 1
24
12 2
14
18 0
19
1000000000 5
2620708101
Первый пример рассмотрен в условии.
Во втором примере $$$12$$$ парковочных мест, а цифра, которую не любит Монокарп, равна $$$2$$$. Таким образом, номера парковочных мест будут выглядеть следующим образом: $$$[1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14]$$$. Поэтому у $$$12$$$-го парковочного места будет номер $$$14$$$.
В третьем примере $$$18$$$ парковочных мест, а цифра, которую не любит Монокарп, равна $$$0$$$. Таким образом, номера парковочных мест будут выглядеть следующим образом: $$$[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19]$$$. Поэтому у $$$18$$$-го парковочного места будет номер $$$19$$$.
Вам дана строка $$$s$$$, состоящая из $$$n$$$ символов. Каждый символ — либо 0, либо 1.
Вы можете проводить операции со строкой. Каждая операция состоит из двух шагов:
Обратите внимание, что в каждой операции оба шага обязательны, и их порядок нельзя менять.
Например, если у вас есть строка $$$s =$$$ 111010, первая операция может быть одной из следующих:
Вы заканчиваете проводить операции, когда строка $$$s$$$ становится пустой. Какое максимальное количество операций вы можете провести?
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина строки $$$s$$$.
Во второй строке задана $$$s$$$ — строка из $$$n$$$ символов. Каждый символ — либо 0, либо 1.
Выведите одно целое число — максимальное количество операций, которые вы можете провести.
6 111010
3
1 0
1
1 1
1
2 11
1
6 101010
3
Вам задана строка $$$s$$$. Вам необходимо перевернуть эту строку. То есть последняя буква строки должна стать первой, предпоследняя буква строки должна стать второй, и так далее. Например, перевернутая строка «abddea» равна «aeddba». Для достижения цели (то есть для переворота заданной строки) вы можете менять местами соседние элементы строки.
Перед вами стоит задача определить минимальное количество обменов соседних элементов строки, необходимых для того, чтобы перевернуть строку.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — длина строки $$$s$$$.
Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.
Выведите минимальное количество обменов соседних элементов строки, необходимых для того, чтобы перевернуть строку.
5 aaaza
2
6 cbaabc
0
9 icpcsguru
30
В первом примере нужно сначала поменять местами третью и четвертую буквы, тогда строка станет равна «aazaa». Затем нужно поменять вторую и третью буквы, тогда строка станет равна «azaaa». Таким образом, за два обмена соседних букв мы сможем перевернуть заданную строку.
Во втором примере заданная строка является палиндромом, то есть перевернутая строка равна исходной строке, поэтому никаких обменов делать не нужно.
У вас есть строка $$$s$$$, состоящая из строчных букв латинского алфавита.
Вам нужно разделить эту строку на подстроки, удовлетворяющие следующим требованиям:
Таким образом, если мы склеим в том же порядке все получившиеся подстроки, то получим исходную строку $$$s$$$.
Подстрока строки $$$s$$$ — это непустая последовательность подряд идущих букв строки $$$s$$$.
Например, строку aadddzxxz можно разделить на подстроки aa, ddd и zxxz.
Определите максимальное количество подстрок, на которые можно разделить строку $$$s$$$, а также размеры каждой из этих подстрок. Если разделить строку $$$s$$$ описанным образом невозможно, сообщите об этом.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$) — длина строки $$$s$$$.
Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.
Если невозможно разделить строку на подстроки длины большей единицы, начинающиеся и заканчивающиеся на одну и ту же букву, выведите $$$-1$$$.
В противном случае, в первую строку выведите $$$k$$$ — максимальное число подстрок, на которые можно разделить строку $$$s$$$. Во вторую строку выведите $$$k$$$ целых чисел — размеры подстрок, на которые можно разделить строку $$$s$$$, в порядке слева направо. Сумма выведенных $$$k$$$ чисел должна быть равна $$$n$$$.
4 aaaa
2 2 2
15 abcbcaccbbcabca
3 6 5 4
4 abcd
-1
5 abcda
1 5
В первом примере можно разделить строку на две подстроки длины два, каждая из которых будет начинаться и заканчиваться буквой a.
Во втором примере можно разделить строку на три подстроки abcbca, ccbbc и abca.
Недавно вам попался на глаза новый шутер. Говорят, данный шутер обладает реалистичными игровыми механиками.
У вашего персонажа есть пистолет с магазином в $$$k$$$ патронов и ему нужно уничтожить $$$n$$$ волн монстров. Волна $$$i$$$ состоит из $$$a_i$$$ монстров и происходит с момента времени $$$l_i$$$ по момент $$$r_i$$$. Все $$$a_i$$$ появляются в момент $$$l_i$$$ и вы должны уничтожить их всех вплоть до момента $$$r_i$$$ (вы можете убивать монстров ровно в момент $$$r_i$$$). Для каждой пары последовательных волн верно, что вторая волна начинается не раньше того момента, в который заканчивается первая волна — формально, выполняется условие $$$r_i \le l_{i + 1}$$$. Прочтите примечания к примерам из условия для более хорошего понимания процесса.
Вы уверены в своих навыках и навыках своего персонажа, а потому можете считать, что прицеливание и стрельба моментальны и что вам нужен ровно один выстрел, чтобы убить одного монстра. Однако перезарядка пистолета занимает ровно $$$1$$$ единицу времени.
Одна из реалистичных механик — это механика перезарядки: когда вы перезаряжаетесь, вы выбрасываете старый магазин вместе с оставшимися патронами. А потому постоянные перезарядки могут привести к трате огромного количества патронов.
Вам понравилась данная механика, и вам стало интересно: какое наименьшее количество патронов необходимо потратить (используя или выбрасывая), чтобы уничтожить все волны.
Заметим, что вы не выбрасываете патроны, оставшиеся после уничтожения всех волн монстров, а также начинаете игру с полным магазином.
В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2000$$$; $$$1 \le k \le 10^9$$$) — количество волн и размер магазина.
В следующих $$$n$$$ строках заданы описания волн. В $$$i$$$-й строке заданы три целых числа $$$l_i$$$, $$$r_i$$$ и $$$a_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$; $$$1 \le a_i \le 10^9$$$) — отрезок времени, когда происходит $$$i$$$-я волна и количество монстров в ней.
Гарантируется, что волны не пересекаются по времени (но могут касаться) и заданы в порядке появления, то есть $$$r_i \le l_{i + 1}$$$.
Если не существует способа зачистить все волны, выведите $$$-1$$$. Иначе, выведите наименьшее количество патронов, которое необходимо потратить (используя или выбрасывая), чтобы уничтожить все волны врагов.
2 3 2 3 6 3 4 3
9
2 5 3 7 11 10 12 15
30
5 42 42 42 42 42 43 42 43 44 42 44 45 42 45 45 1
-1
1 10 100 111 1
1
В первом примере:
Во втором примере:
Дан ориентированный ацикличный граф (ориентированный граф, не содержащий циклов) из $$$n$$$ вершин и $$$m$$$ дуг. $$$i$$$-я дуга ведет из вершины $$$x_i$$$ в вершину $$$y_i$$$ и имеет вес $$$w_i$$$.
Ваша задача — для каждой вершины $$$v$$$ выбрать некоторое целое число $$$a_v$$$, после чего на каждой дуге $$$i$$$ записать такое число $$$b_i$$$, что $$$b_i = a_{x_i} - a_{y_i}$$$. Вы должны выбрать числа таким образом, чтобы:
Можно показать, что для любого ориентированного ацикличного графа с неотрицательными $$$w_i$$$ такой способ выбрать числа существует.
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 18$$$; $$$0 \le m \le \dfrac{n(n - 1)}{2}$$$).
Далее следуют $$$m$$$ строк, $$$i$$$-я из них содержит три целых числа $$$x_i$$$, $$$y_i$$$ и $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$1 \le w_i \le 10^5$$$, $$$x_i \ne y_i$$$) — описание $$$i$$$-й дуги.
Гарантируется, что строки задают описание $$$m$$$ дуг ориентированного ацикличного графа без кратных дуг.
Выведите $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_v \le 10^9$$$), которые необходимо записать на вершинах, чтобы все $$$b_i$$$ были положительны, и значение выражения $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ было минимально возможным. Если ответов несколько — выведите любой. Можно показать, что ответ всегда существует, и хотя бы один из оптимальных ответов удовлетворяет ограничениям $$$0 \le a_v \le 10^9$$$.
3 2 2 1 4 1 3 2
1 2 0
5 4 1 2 1 2 3 1 1 3 6 4 5 8
43 42 41 1337 1336
5 5 1 2 1 2 3 1 3 4 1 1 5 1 5 4 10
4 3 2 1 2