После масштабного финансового успеха владелец компании 'Nikola' принял решение предложить департаменту полиции Берляндии беспилотные автомобили, оснащённые радаром, которые измеряют скорость проезжающих мимо машин. По мнению владельца компании, такие автомобили помогут поддерживать дисциплину на дорогах государства.
Известно, что беспилотный автомобиль движется со скоростью $$$x$$$ км/ч, а ограничение скорости составляет $$$y$$$ км/ч $$$(y \ge x)$$$. Проблема радара заключается в том, что он измеряет, с какой скоростью относительно него движутся проезжающие автомобили, а также не различает, обгоняет ли автомобиль полицейскую машину (или вообще движется навстречу) или наоборот — радар лишь записывает скорость.
Вам поручили написать программу, которая определяет, сколько правонарушений зафиксировал беспилотный автомобиль. Правонарушением называется ситуация, когда скорость автомобиля относительно земли строго больше ограничения скорости.
Так как данные неоднозначны и один результат может быть зачтен по-разному в зависимости от направления движения и/или реальной скорости автомобиля, выведите минимально возможное количество правонарушений и максимально возможное количество правонарушений, зафиксированных беспилотником.
На первой строке подается число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество замеров скорости, совершенных беспилотником.
На второй строке подается число $$$x$$$ $$$(1 \le x \le 10^5)$$$ — скорость беспилотника.
На третьей строке подается число $$$y$$$ $$$(1 \le y \le 10^5)$$$ — ограничение скорости. Гарантируется, что $$$x \le y$$$.
На следующих $$$n$$$ строках подается по одному целому числу $$$s_i$$$ $$$(1 \le s_i \le 10^5)$$$ — результат очередного замера.
Выведите на одной строке через пробел два числа — минимально возможное и максимально возможное количество зафиксированных правонарушений соответственно.
| № | Баллы | Ограничения | Необх. подзадачи | Результаты |
| 1 | 100 | - | - | потестовые |
2 50 70 60 15
0 1
Если первая машина движется по пути следования полицейской машины, то ее скорость относительно земли составляет $$$50 + 60 = 110$$$ км/ч — превышение. Также она могла двигаться навстречу: тогда ее скорость равна лишь $$$10$$$ км/ч.
Скорость второй машины относительно земли составляет $$$50 + 15 = 65$$$ км/ч — не превышение или $$$50 - 15 = 35$$$ км/ч — тоже не превышение (в обоих случаях она ехала по пути следования полицейской машины).
Несмотря на глобальную пандемию, Дед Мороз всё же решил раздать подарки детям на Новый год. Оказалось, что подарки нужно вручить $$$n$$$ мальчикам и $$$m$$$ девочкам. Подарки он создаёт с помощью заклинаний и волшебной палочки; причём оказалось так, что на подарки для мальчиков и подарки для девочек он тратит разное количество времени — $$$x$$$ минут и $$$y$$$ минут на один подарок соответственно.
Кроме того, есть подарки, которые Дед Мороз считает универсальными — подходящими и для девочек, и для мальчиков — на их подготовку у него уходит тоже определённое количество времени, и оно составляет $$$z$$$ минут.
Но, к сожалению, так оказалось, что в его волшебные сани может поместиться только $$$k$$$ подарков, которые подходят и для мальчиков, и для девочек одновременно. Зная это, помогите Деду Морозу понять, сколько времени ему нужно будет минимально потратить на подготовку подарков.
Вводится шесть строк.
На первой строке подается целое число $$$n$$$ — количество мальчиков.
На второй строке подается целое число $$$m$$$ — количество девочек.
На третьей строке подается целое число $$$x$$$ — время, необходимое для создания подарка для мальчиков.
На четвертой строке подается целое число $$$y$$$ — время, необходимое для создания подарка для девочек.
На пятой строке подается целое число $$$z$$$ — время, необходимое для создания подарка, подходящего и для мальчиков, и для девочек.
На шестой строке подается целое число $$$k$$$ — наибольшее количество 'универсальных' подарков, которое Дед Мороз может увезти с собой.
Числа не превосходят $$$10^9$$$.
Выведите единственное число — минимальное количество минут, которое нужно Деду Морозу, чтобы каждому ребёнку достался подходящий подарок.
| № | Баллы | Ограничения | Необх. подзадачи | Результаты |
| 1 | 17 | $$$k = 0$$$ | - | потестовые |
| 2 | 24 | $$$m = 0$$$ | - | потестовые |
| 3 | 34 | $$$n, m, k, x, y, z \le 100$$$ | - | потестовые |
| 4 | 10 | $$$n, m, k, x, y, z \le 10^5$$$ | - | потестовые |
| 5 | 15 | $$$n, m, k, x, y, z \le 10^9$$$ | - | потестовые |
9 17 4 3 2 10
68
10 10 5 7 6 500
110
В первом примере оптимально заменить все подарки для мальчиков на универсальные, а также подарить универсальный подарок одной девочке. Итого $$$9 \cdot 2 + 1 \cdot 2 + 16 \cdot 3 = 68$$$ минут.
Во втором примере оптимально заменить только подарки для девочек, потому что подарки для мальчиков Дед Мороз умеет готовить быстро.
В семье физика-нанотехнолога Дианы готовятся к наступлению Нового года. Чтобы полакомиться в новогоднюю ночь, Диана испекла для двух её лучших друзей — Вовы и Гриши — пирог в форме правильного многоугольника с $$$n$$$ сторонами.
Тут она вспомнила, что Вове нравятся пироги в виде $$$a$$$-угольников (необязательно правильных), а Грише — пироги в виде $$$b$$$-угольников. Может ли Диана одним разрезом ножа разделить её пирог на две части, представляющие собой многоугольники ненулевой площади, в одном из которых $$$a$$$ сторон, а в другом $$$b$$$ сторон?
На первой строке подаётся число $$$n$$$ $$$(3 \le n \le 10^9)$$$ — количество сторон у пирога.
На второй строке подаётся число $$$a$$$ $$$(3 \le a \le 10^9)$$$ — количество сторон, которое нравится Вове.
На третьей строке подаётся число $$$b$$$ $$$(3 \le b \le 10^9)$$$ — количество сторон, которое нравится Грише.
Выведите YES, если Диана может разрезать пирог так, чтобы обоим гостям понравились их кусочки, и NO в противном случае.
| № | Баллы | Ограничения | Необх. подзадачи | Результаты |
| 1 | 18 | $$$n = 3$$$ | - | подзадача |
| 2 | 22 | $$$n \le 5$$$ | 1 | подзадача |
| 3 | 45 | $$$n \le 100$$$ | 1, 2 | подзадача |
| 4 | 15 | $$$n \le 10^9$$$ | 1, 2, 3 | подзадача |
4 3 3
YES
4 4 4
YES
Диана может разрезать квадратный пирог по диагонали и получить два треугольника. Они не будут правильными — на самом деле, они будут прямоугольными — но по условия задачи это не имеет значения.
Кот Матроскин решил поступить в университет и для этого собрал документы (за исключением, конечно же, ушей, лап и хвоста). Всего у него было $$$m$$$ документов, и их он пронумеровал от $$$1$$$ до $$$m$$$: каждому документу достался уникальный номер.
К сожалению, по пути в университет он поскользнулся и рассыпал документы. Собрав документы, он понял, что одного документа не хватает. Он не может быстро определить, документ с каким номером пропал. Однако он может быстро посчитать сумму номеров документов, которые у него остались. Кроме того, Матроскин подавал документы в целых $$$t$$$ вузов, и каждый раз с ним происходил такой конфуз. Помогите коту Матроскину понять, документы под каким номерами был потеряны им и требуют срочного восстановления!
На первой строке вводится единственное число $$$(1 \le t \le 10^5)$$$ — количество вузов, в которые подал документы Матроскин.
На последующих $$$t$$$ строках вводится единственное число $$$(1 \le n \le 10^9)$$$ — сумма номеров документов, которые остались у Матроскина.
Выведите для каждого тестового примера число — номер документа, который Матроскин потерял. Если ответов несколько, выведите любой из них.
| № | Баллы | Ограничения | Необх. подзадачи | Результаты |
| 1 | 44 | $$$n \le 1000, t = 1$$$ | - | потестовые |
| 2 | 25 | $$$n \le 10^9, t = 1$$$ | - | подзадача |
| 3 | 31 | $$$n \le 10^9, t \le 10^5$$$ | - | подзадача |
1 4
2
2 4 6
2 4
В первом примере могло случиться так, что он потерял документ под номером $$$2$$$, а остались у него документы под номером $$$1$$$ и $$$3$$$.
Вася очень хотел съездить на заключительный этап Всероссийской олимпиады по информатике. Настолько сильно, что соврал своему другу Пете, что съездил. Более того, он сказал ему: 'По результатам только первого дня я занял $$$a$$$-ое место, по результатам только второго дня я занял $$$b$$$-ое место, а в итоговой таблице я оказался $$$c$$$-ым, причем ни с кем я эти места не разделял!'
Так как Вася врал Пете уже много раз, он ему не поверил и попросил показать таблицу результатов. Помогите Васе придумать такую таблицу результатов олимпиады (сам он этого сделать не может, потому что на регионе даже не набрал сто баллов), чтобы в ней выполнялись условия, которые он озвучил Пете.
На единственной строке подаются три целых числа: $$$a, b, c$$$ $$$(1 \le a, b, c \le 50000)$$$ — место Васи по результатам первого дня, место Васи по результатам второго дня, место Васи в итоговой таблице с суммой баллов за оба дня.
Если необходимой таблицы не существует и Васе будет необходимо признать фиаско, то выведите -1.
Если такая таблица существует, то на первой строке выведите $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$ — количество участников олимпиады. Далее на $$$n$$$ последующих строках выведите по три числа: на $$$i + 1$$$-й строке — результат $$$i$$$-ого участника в баллах за первый день, за второй день и за оба дня соответственно. Результаты участников можно выводить в любом порядке. В каждой колонке результат Васи должен быть уникален. Обратитесь к примерам для лучшего понимания.
| № | Баллы | Ограничения | Необх. подзадачи | Результаты |
| 1 | 10 | $$$a = b = c$$$ | - | потестовые |
| 2 | 60 | $$$1 \le a, b, c \le 100$$$ | - | потестовые |
| 3 | 30 | $$$1 \le a, b, c \le 50000$$$ | - | потестовые |
4 1 2
5 100 200 300 130 160 290 110 155 265 56 72 128 240 180 420
Предоставим пример с пятью участниками. Васиному выступлению на олимпиаде соответствует первая тройка чисел. Действительно, в первый день он показал четвертый результат, во второй день — наилучший, а по сумме двух дней пришёл вторым.
Недавно открывшийся отель "Шевалье" принимает туристов. В отеле находится $$$n$$$ номеров различной вместительности, $$$i$$$-й номер имеет вместительность $$$c_i$$$. Снять номер желает $$$k$$$ компаний, $$$j$$$-ая компания состоит из $$$p_j$$$ человек и готова заплатить за номер $$$m_j$$$ долларов. Компания может поместиться в номер, если ее размер не больше, чем вместительность номера. Кроме того, в одном номере может проживать не более одной компании.
К сожалению, может случиться такое, что отель недостаточно велик, чтобы разместить у себя все компании туристов. Помогите менеджеру отеля получить максимальную прибыль, написав программу, которая оптимально расселит компании по номерам.
На первой строке подается два целых числа $$$n$$$, $$$k$$$ $$$(1 \le n, k \le 150000)$$$ — количество номеров в отеле и количество компаний потенциальных гостей.
На второй строке подается $$$n$$$ целых чисел $$$c_i$$$ $$$(1 \le c_i \le 100000)$$$ — вместительность комнат.
На третьей строке подается $$$k$$$ целых чисел $$$p_i$$$ $$$(1 \le p_i \le 100000)$$$ — количество туристов в каждой компании.
На четвертой строке подается $$$k$$$ целых чисел $$$m_i$$$ $$$(1 \le m_i \le 100000)$$$ — количество денег, которое готовы заплатить компании туристов за размещение.
Выведите единственное число — максимальное количество денег, которое может получить отель в результате размещения в комнатах приехавших туристов.
| № | Баллы | Ограничения | Необх. подзадачи | Результаты |
| 1 | 20 | $$$n \le 10, k \le 10$$$ | - | подзадача |
| 2 | 14 | $$$c_i \le 2$$$ | - | подзадача |
| 3 | 19 | $$$m_i = 1$$$ | - | подзадача |
| 4 | 46 | $$$n \le 1000, k \le 1000$$$ | - | подзадача |
| 5 | 1 | $$$n \le 150000, k \le 150000$$$ | 1, 2, 3, 4 | подзадача |
2 4 3 5 2 4 5 6 9 10 8 22
19