В городе Старая Деревня всего две улицы, и по обеим разрешено движение только в одном направлении. На перекрестке этих улиц установлен единственный в городе светофор. В любой момент времени светофор разрешает движение по одной из двух улиц, а по другой — запрещает.
Вам известен поминутный режим работы светофора. Этот режим описывается строкой $$$s$$$ длины $$$n$$$, состоящей из цифр $$$1$$$ и $$$2$$$. Если $$$s_i = 1$$$, то в течение $$$i$$$-й минуты с начала работы светофор разрешает движение по первой улице, а иначе — по второй. После $$$n$$$-й минуты светофор начинает цикл режима работы с начала, то есть, в течение $$$(n + 1)$$$-й минуты он разрешает движение по той же улице, что и в течение $$$1$$$-й, в течение $$$(n + 2)$$$-й — по той же, что и в течение $$$2$$$-й минуты, и так далее.
Вы знаете, что всего в течение дня $$$m$$$ машин подъедут к светофору. $$$i$$$-я из этих машин подъедет в момент времени $$$t_i$$$ по одной из двух улиц. Машины на каждой улице образуют очередь и ожидают разрешающего сигнала светофора. В течение одной минуты через перекресток может проехать максимум одна машина по той улице, по которой движение разрешено, и ни одной машины по другой улице.
Вам необходимо выбрать для каждой машины, по какой улице необходимо подъехать, чтобы суммарное время ожидания всех машин было минимально возможным.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$k$$$ ($$$1 \le k \le 1000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — период работы светофора и количество машин, соответственно.
Вторая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую из цифр $$$1$$$ и $$$2$$$ — режим работы светофора.
Третья строка содержит $$$m$$$ целых чисел $$$t_1$$$, $$$t_2$$$, ..., $$$t_m$$$ ($$$0 \le t_i \le 10^5$$$) — моменты времени, в которые машины подъезжают к перекрестку. Если машины приехала в момент времени $$$x$$$, то проехать перекресток она может не раньше, чем в $$$(x + 1)$$$-ю минуту. Если несколько машин подъезжают одновременно, они выстраиваются в очередь в порядке номеров.
Гарантируется, что сумма значений $$$n$$$, а также сумма значений $$$m$$$ по всем наборам входных данных не превосходят $$$10^5$$$.
Для каждого набора входных данных выведите две строки. В первой выведите одно целое число $$$w$$$ — суммарное время ожидания всех машин в оптимальном решении.
Во второй строке выведите $$$m$$$ целых чисел $$$s_1$$$, $$$s_2$$$, ..., $$$s_m$$$, где $$$s_i = 1$$$, если $$$i$$$-я машина должна подъехать по первой дороге, и $$$2$$$ иначе. Если существует несколько решений, выведите любое из них.
В тестах суммарной стоимостью не менее 16 баллов дополнительно выполняется: сумма значений $$$n$$$, сумма значений $$$m$$$ во всех наборах входных данных не превосходят $$$20$$$; $$$t_i \le 20$$$.
В тестах суммарной стоимостью не менее 36 баллов дополнительно выполняется: сумма значений $$$n$$$, сумма значений $$$m$$$ во всех наборах входных данных не превосходят $$$300$$$; $$$t_i \le 300$$$.
В тестах суммарной стоимостью не менее 56 баллов дополнительно выполняется: сумма значений $$$n$$$, сумма значений $$$m$$$ во всех наборах входных данных не превосходят $$$5000$$$.
33 51210 0 5 2 41 420 0 0 06 62221110 0 2 2 1 1
1 1 2 1 1 2 6 2 2 2 2 9 2 2 1 1 2 1
В первом примере ожидать зеленого сигнала будет только вторая машина в течение одной минуты, остальные проедут перекресток без остановки.
Во втором примере светофор всегда запрещает проезд по первой дороге, поэтому все машины необходимо отправить по второй дороге. Машины будут ожидать соответственно $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ минуты в очереди.
Дмитрий и Анна — муж и жена. Как это нередко бывает, они являются гражданами разных стран. В каждой из этих стран применяется прогрессивная система налогообложения.
А именно, в стране Дмитрия система налогообложения на доход физических лиц устроена следующим образом:
- сумма дохода, не превосходящая $$$a_1$$$, облагается налогом в размере $$$p_1$$$%;
- часть дохода, превышающая $$$a_1$$$, до общего дохода $$$a_2$$$, облагается налогом в размере $$$p_2$$$%;
- часть дохода, превышающая $$$a_2$$$, до общего дохода $$$a_3$$$, облагается налогом в размере $$$p_3$$$%, и так далее,
- наконец, часть дохода, превышающая $$$a_n$$$, облагается налогом в размере $$$p_{n+1}$$$%.
Например, если $$$n=3$$$, $$$a_1=100$$$, $$$a_2=300$$$, $$$a_3=1000$$$, и $$$p_1=10$$$, $$$p_2=12$$$, $$$p_3=14$$$, $$$p_4=16$$$, и общий доход составляет $$$1234$$$, то этот доход делится на следующие части: сумма $$$100$$$ облагается налогом в размере $$$10$$$%, сумма $$$200$$$ (т. е. от $$$100$$$ до $$$300$$$) облагается налогом $$$12$$$%, сумма $$$700$$$ (т. е. от $$$300$$$ до $$$1000$$$) — налогом $$$14$$$%, и оставшаяся сумма $$$234$$$ (от $$$1000$$$ до $$$1234$$$) — налогом $$$16$$$%. Итоговая сумма налога равна $$$100\cdot 0.10+200\cdot 0.12+700\cdot 0.14+234\cdot 0.16=169.44$$$.
Аналогично, если общий доход составляет $$$50$$$, то налог будет равен $$$50\cdot 0.10=5$$$, а если общий доход составляет ровно $$$300$$$, то налог будет равен $$$100\cdot 0.10+200\cdot 0.12=34$$$.
В стране Анны действует аналогичная система, но с другими параметрами:
- сумма дохода, не превосходящая $$$b_1$$$, облагается налогом в размере $$$q_1$$$%;
- часть дохода, превышающая $$$b_1$$$, до общего дохода $$$b_2$$$, облагается налогом в размере $$$q_2$$$%;
- часть дохода, превышающая $$$b_2$$$, до общего дохода $$$b_3$$$, облагается налогом в размере $$$q_3$$$%, и так далее,
- наконец, часть дохода, превышающая $$$b_m$$$, облагается налогом в размере $$$q_{m+1}$$$%.
За прошлый год суммарный доход Дмитрия и Анны равен $$$X$$$. Теперь они должны уплатить налоги с него. Конкретно, Дмитрий может задекларировать некоторую сумму дохода $$$t$$$, и уплатить с него налог согласно налоговому законодательству страны Дмитрия, а Анна тогда задекларирует сумму дохода, равную $$$X-t$$$, и уплатит с нее налог согласно налоговому законодательству страны Анны.
Помогите им задекларировать доход так, чтобы суммарный уплаченный доход был как можно меньше.
Первая строка содержит одно целое число $$$n$$$ — количество «уровней» налогов в стране Дмитрия ($$$0 \leq n \leq 100\,000$$$).
На второй строке находятся $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — пороговые суммы в законодательстве страны Дмитрия ($$$1\leq a_i\leq 10^{16}$$$; гарантируется, что $$$a_i \lt a_{i+1}$$$ для каждого $$$i$$$).
На третьей строке находится $$$n+1$$$ целое число $$$p_1$$$, $$$p_2$$$, ..., $$$p_{n+1}$$$ — ставки налогов в стране Дмитрия ($$$0\leq p_i\leq 100$$$).
Следующие три строки содержат описание налогового законодательства страны Анны в том же формате (на первой из них одно число $$$m$$$, на следующей $$$m$$$ чисел $$$b_1$$$, $$$b_2$$$, ..., $$$b_m$$$, на следующей $$$m+1$$$ число $$$q_1$$$, $$$q_2$$$, ..., $$$q_{m+1}$$$; ограничения на эти числа аналогичны ограничениям на параметры страны Дмитрия).
На седьмой строке входных данных находится одно целое число $$$X$$$ — суммарный доход Дмитрия и Анны ($$$0\leq X\leq 10^{16}$$$).
Обратите внимание, что $$$n$$$ и/или $$$m$$$ могут быть равны нулю (плоская система налогообложения). В таком случае строки с числами $$$a_i$$$ и/или $$$b_i$$$ будут пустыми.
Выведите одно целое число $$$t$$$ — размер дохода, который должен задекларировать Дмитрий для минимизации суммарного налога. Если существует несколько оптимальных решений, выведите любое из них.
В тестах общей стоимостью не менее 10 баллов дополнительно выполняется $$$n=m=0$$$.
В тестах общей стоимостью не менее 10 баллов дополнительно выполняется $$$n=m=1$$$.
В тестах общей стоимостью не менее 20 баллов дополнительно выполняется $$$p_{i+1}\geq p_i$$$ и $$$q_{i+1}\geq q_i$$$ для всех $$$i$$$ (массивы $$$p$$$ и $$$q$$$ не убывают).
В тестах общей стоимостью не менее 40 баллов дополнительно выполняется $$$n\leq 1000$$$ и $$$m \leq 1000$$$.
1 10 12 17 2 20 40 15 17 20 50
20
1 10 10 20 0 30 50
50
В первом примере Дмитрий платит $$$10\cdot 0.12+10\cdot 0.17=2.9$$$, а Анна платит $$$20\cdot0.15 + 10\cdot 0.17=4.7$$$, суммарный налог получается $$$7.6$$$.
Во втором примере оптимально задекларировать весь доход в стране Дмитрия. В этом случае суммарный налог будет равен $$$50 \cdot 0.2 = 10$$$.
Однажды летом Ёжик отправился в Индокитай, чтобы познакомиться с местными достопримечательностями и найти своих сородичей. Прогуливаясь по джунглям в поисках сородичей, он нашёл кобру и решил её почесать.
Из надёжных источников Ёжик узнал, что кобра делится на $$$n$$$ последовательных сегментов, пронумерованных от $$$1$$$ до $$$n$$$. За один шаг Ёжик может выбрать какой-то один сегмент и почесать его. Ёжик может почесать несколько сегментов один за другим, однако кобра не всегда этому рада. Непосредственно после того, как Ёжик почесал $$$i$$$-й сегмент, недовольство кобры становится равным $$$a_i$$$, и Ёжик не может почесать никакой из первых $$$a_i$$$ сегментов. Иными словами, если Ёжик подряд чешет сегменты $$$i$$$, затем $$$j$$$, то должно выполняться $$$j \gt a_i$$$.
Вместе с тем Ёжик знает, что ночью недовольство кобры опускается до нуля, и на следующее утро кобра снова позволит почесать любой сегмент независимо от того, какой сегмент Ёжик чесал последним в предыдущий день.
Как опытный исследователь, Ёжик решил почесать каждый сегмент кобры ровно по одному разу, даже если на это понадобится несколько дней. Определите, какое минимальное количество дней ему понадобится. Выведите это количество и для каждого дня выведите сегменты, которые в этот день в выбранном вами порядке нужно почесать.
В первой строке задано одно целое число $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — количество сегментов.
В следующей строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$), где $$$a_i$$$ — количество недоступных сегментов после выбора $$$i$$$-го.
В первой строке выведите минимальное количество дней $$$t$$$, которое нужно, чтобы почесать все сегменты.
Далее выведите $$$t$$$ строк. В $$$i$$$-й строке выведите целое неотрицательное число $$$k_i$$$, затем $$$k_i$$$ целых чисел — номера сегментов, которые нужно почесать в $$$i$$$-й день в соответствующем порядке.
Если существуют несколько оптимальных решений, выведите любое.
Каждый пройденный тест оценивается независимо некоторым количеством баллов. Все тесты разделены на группы, в большинстве из них есть дополнительные ограничения на входные данные. Ниже приведена таблица, где указаны эти ограничения и суммарная стоимость тестов в каждой группе.
| Группа | Доп. ограничения | Баллы |
| $$$1$$$ | $$$n \le 8$$$ | $$$10$$$ |
| $$$2$$$ | $$$n \le 17$$$ | $$$7$$$ |
| $$$3$$$ | $$$a_i \ge i$$$ | $$$15$$$ |
| $$$4$$$ | $$$a$$$ содержит все числа от $$$0$$$ до $$$n-1$$$ | $$$8$$$ |
| $$$5$$$ | Гарантируется, что существует ответ с $$$t = 1$$$ | $$$30$$$ |
| $$$6$$$ | — | $$$30$$$ |
4 3 2 4 4
2 2 2 3 2 1 4
5 5 1 1 1 2
2 4 5 4 3 2 1 1
В первом примере Ёжик может почесать кобру за $$$2$$$ дня, например, так.
- В начале первого дня недовольство кобры равно $$$0$$$.
- Ёжик выбирает $$$1$$$-й сегмент кобры, недовольство кобры становится равным $$$3$$$.
- Ёжик выбирает $$$4$$$-й участок кобры, недовольство кобры становится равным $$$4$$$. Больше Ёжик не может выбрать никакой сегмент в этот день.
- Во второй день недовольство кобры снова становится равным $$$0$$$, поэтому можно выбрать любой сегмент.
- Ёжик сначала выбирает $$$2$$$-й участок кобры, недовольство кобры становится равным $$$2$$$.
- Затем Ёжик выбирает $$$3$$$-й участок кобры, недовольство кобры становится равным $$$4$$$.
В одном известном Берляндском лицее есть традиция: каждый день записывать на доске в актовом зале число дня! Но ребятам-программистам не нравилось, что ребята-хронометристы постоянно пишут числа, кратные 60, а им в свою очередь не нравилась привычка ребят-программистов писать степени двойки.
После долгих месяцев споров ребята пришли к компромиссу: в $$$i$$$-й день они пишут на доске $$$i$$$-е по возрастанию число, представимое в виде $$$2^k + 60 \cdot m$$$ для каких-либо натуральных $$$k$$$ и $$$m$$$.
Завхоз лицея прекрасно понимает, что мел — не самое дешёвое удовольствие, поэтому он просит вас помочь ему понять, какое число будет написано в день $$$n$$$, а с необходимым количеством мела он уже разберётся сам.
В единственной строке находится одно целое число $$$n$$$ ($$$1 \leq n \leq 10^{15}$$$) — номер дня, для которого вам нужно определить число, которое должно быть написано на доске.
Выведите число, которое будет написано на доске в день $$$n$$$.
В тестах суммарной стоимостью не менее $$$10$$$ баллов дополнительно выполняется $$$n \leq 100$$$.
В тестах суммарной стоимостью не менее $$$25$$$ баллов дополнительно выполняется $$$n \leq 100\,000$$$.
1
62
13
188
Офис одной из IT-компаний при виде сверху представляет собой квадрат со сторонами длины $$$n$$$. Для удобства введем систему координат и расположим на ней офис так, что левый-нижний угол офиса будет иметь координаты $$$(0,0)$$$, а правый-верхний — координаты $$$(n,n)$$$. При этом левая стена офиса лежит на оси $$$OY$$$, а нижняя — на оси $$$OX$$$ (см. рисунок ниже). Правой и верхней стен в офисе нет, вместо них по всей длине стороны квадрата расположены окна.
Приближается лето, поэтому солнце всё чаще заглядывает в офис. Лучи солнца движутся в направлении вектора $$$(x_s,y_s)$$$. Можно считать, что солнце достаточно большое и через каждую точку проходит ровно один такой луч.
В офисе расположены $$$k$$$ компьютерных столов, каждый из которых можно представить в виде отрезка. Лучи солнца проходят через окна и попадают на компьютерные столы. Конечно, это доставляет неудобства разработчикам и препятствует развитию IT-индустрии. Для устранения проблемы было решено применить инновационный метод — занавески. Занавески можно вешать на окна и тем самым частично блокировать проникновение лучей в офис. Более формально, любую часть окон можно завесить занавесками; если луч света попадает на занавеску, то он не проходит в офис. На картинке ниже красным цветом отмечена занавеска, которая блокирует попадание на стол лучей солнца, движущихся вдоль вектора $$$(-2, 0)$$$:
Разумеется, нужно повесить занавески таким образом, чтобы лучи солнца не попали ни на один компьютерный стол. С другой стороны, разработчики соскучились по ярким летним дням, поэтому суммарная длина занавесок должна быть минимально возможной. Помогите IT-индустрии — найдите эту длину!
В первой строке записаны три целых числа $$$n$$$, $$$x_s$$$ и $$$y_s$$$ ($$$2 \leq n \leq 10^9$$$, $$$-10^9 \leq x_s, y_s \leq 0$$$, $$$x_s + y_s \lt 0$$$) — размер офиса и направление лучей солнца.
Вторая строка содержит одно целое число $$$k$$$ ($$$1 \leq k \leq 2\cdot 10^5$$$) — количество столов в офисе.
В каждой из следующих $$$k$$$ строк записаны 4 натуральных числа $$$x_{1i}$$$, $$$y_{1i}$$$, $$$x_{2i}$$$, $$$y_{2i}$$$ ($$$0 \lt x_{1i}, y_{1i}, x_{2i}, y_{2i} \lt n$$$), обозначающие координаты одного конца стола $$$(x_{1i}, y_{1i})$$$ и координаты другого конца стола — $$$(x_{2i}, y_{2i})$$$. Столы могут пересекаться или даже совпадать.
Выведите единственное вещественное число — минимальную суммарную длину занавесок.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$.
Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
В тестах общей стоимостью не менее 30 баллов дополнительно выполняется $$$x_s=0$$$ или $$$y_s=0$$$.
В тестах общей стоимостью не менее 30 баллов дополнительно выполняется $$$k=1$$$.
6 -2 0 1 2 1 4 2
1.000000
6 0 -2 1 2 1 4 2
2.000000
6 -2 -1 1 2 1 4 2
0.000000
6 -2 -3 2 2 1 4 2 1 3 2 3
2.666667
6 -2 -3 2 2 1 4 2 1 3 4 3
4.000000
Картинка в условии соответствует первому примеру.
Во втором примере расположение стола такое же, как и в первом, но лучи солнца движутся вертикально:
В третьем примере стол расположен параллельно лучам солнца, поэтому требуется занавеска длины 0:
В четвертом примере для каждого стола требуется отдельная занавеска:
В пятом примере одна занавеска защищает оба стола от попадания солнечных лучей:
Перспективный пилот Максим участвует в гонке Формулы-100500 из $$$n$$$ кругов. Известно, что свежесть шин играет большую роль в скорости болида, поэтому все комплекты шин имеют параметр изношенности. Если Максим стартует круг на шинах изношенности $$$x$$$, то он проезжает этот круг за $$$x$$$ секунд, а изношенность этого комплекта шин в конце круга становится $$$x + 1$$$.
Всего у команды Максима есть два комплекта шин, первый комплект имеет изношенность $$$a$$$ и уже установлен на болид перед началом гонки. Запасной комплект имеет изношенность $$$b$$$. Перед каждым кругом Максим может сделать пит-стоп и сменить комплект шин на своей машине за $$$p$$$ секунд. Можно делать сколько угодно пит-стопов, в том числе можно сделать пит-стоп перед первым кругом и начать гонку на запасном комплекте, но время этого пит-стопа также будет добавлено к времени гонки.
Ваша задача — помочь Максиму выиграть кубок текущего сезона. Найдите минимально возможное время прохождения $$$n$$$ кругов с имеющимися комплектами шин.
В первой строке находятся четыре целых числа $$$n$$$, $$$a$$$, $$$b$$$ и $$$p$$$ ($$$1 \leq n, a, b, p \leq 10^9$$$) — количество кругов, изношенность начального и запасного комплекта шин, а также время замены комплекта шин.
Выведите минимальное время прохождения дистанции.
В тестах общей стоимостью не менее 10 баллов дополнительно выполняется $$$n, a, b, p \leq 100$$$.
В тестах общей стоимостью не менее 20 баллов дополнительно гарантируется, что оптимально проехать все круги на одном комплекте шин.
В тестах общей стоимостью не менее 25 баллов дополнительно выполняется $$$n, a, b, p \leq 10\,000$$$.
В тестах общей стоимостью не менее 45 баллов дополнительно выполняется $$$n, a, b, p \leq 1\,000\,000$$$.
5 1 10 3
15
6 11 3 10
43
4 3 2 2
14
852902052 192056973 520886218 899744483
458863665239592593
Вася играет в Doublo II. В этой игре предметы можно улучшать при помощи магических камней. Камни бывают разных размеров, причем каждый размер камня — натуральное число.
Чем больше размер камня, тем сильнее эффект от улучшения, поэтому не удивительно, что большие камни встречаются реже и ценятся больше. Однако Вася не расстраивается, когда при прохождении очередного подземелья находит только камни маленьких размеров. Дело в том, что камни можно объединять, тем самым получая камни крупнее. А именно: три камня любого размера $$$k$$$ можно объединить и получить один камень размера $$$k+1$$$ (разумеется, при этом три камня размера $$$k$$$ пропадут).
Камни Васи могут находиться в двух местах — в инвентаре или в сундуке. За одну секунду Вася может переложить один камень любого размера из инвентаря в сундук или наоборот. Также за одну секунду Вася может объединить три камня одинакового размера в один камень большего размера, как описано выше. Однако три камня можно объединить только в том случае, если все они находятся в одном месте: все в инвентаре или все в сундуке. Объединять камни из инвентаря с камнями из сундука запрещается.
Вася планирует навести порядок в своих предметах, поэтому он хочет объединить камни так, чтобы в итоге у него осталось как можно меньше камней (возможно, для этого также потребуется перекладывать камни). Посчитайте, какое наименьшее число секунд ему для этого потребуется, если он будет действовать оптимально.
В первой строке находится целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — максимальный размер камней, который Вася до сих пор встречал в игре.
Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — количество камней размера $$$1, 2, \dots, n$$$ в инвентаре Васи.
В третьей строке находятся $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — количество камней размера $$$1, 2, \dots n$$$ в сундуке.
Обратите внимание, что в процессе объединения можно получать камни размера больше $$$n$$$.
Выведите единственное число — минимальное количество секунд, которое потребуется Васе для получения минимального количества камней.
В тестах общей стоимостью не менее 30 баллов дополнительно выполняется $$$n \leq 15$$$, $$$a_i, b_i \leq 15$$$.
3 0 2 0 3 0 1
3
5 2 1 0 2 2 2 2 0 2 1
6