--->
39 задач
<---
Источники
Обратные задачи представляют собой быстро развивающуюся область информатики. В отличии
от классической постановки задачи, где по заданным исходным данным \(D\) требуется решить некоторую оптимизационную задачу \(P\), в обратной задаче по заданной задаче \(P\) и результату вычисления
\(R\) требуется подобрать исходные данные \(D\), на которых достигается этот результат. В этой задаче
вам предлагается решить обратную задачу к задаче о минимуме на отрезке (range minimum query,
RMQ).
Пусть задан массив \(a[1..n]\). Ответ на запрос о минимуме на отрезке \(Q(i, j)\) — это минимальное
среди значений \(a[i]\), ..., \(a[j]\). Вам дано \(n\) и последовательность запросов о минимуме на отрезке с
ответами. Восстановите исходный массив \(a\).
Первая строка входного файла содержит \(n\) — размер массива, и \(m\) — количество запросов (\(1 \leq n, m \leq 100000\)). Следующие \(m\) строк содержат по три целых числа: числа \(i\), \(j\) и \(q\) означают, что \(Q(i, j) = q\) (\(1 \leq i \leq j \leq n\), \(-2^{31} \leq q \leq 2^{31} - 1\)).
Если входные данные несовместны, то есть искомого массива a не существует, выведите
"inconsistent" на первой строке выходного файла.
В противном случае выведите “consistent” на первой строке выходного файла. Вторая строка
должна содержать сам массив. Элементы массива должны быть целыми числами между \(2^{31}\) и \(2^{31}-1\). Если решений несколько, выведите любое.
Баллы за эту задачу будут начислены только если решение проходит все тесты
3 2 1 2 1 2 3 2
consistent 1 2 2
3 3 1 2 1 1 1 2 2 3 2
inconsistent
У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за \(S\) рублей!
Конечно, скидываться придется всем поровну. То есть, если Коля позовет \(k\) своих друзей, то каждому придется заплатить \(S/(k + 1)\) рублей (да, сам Коля тоже должен внести свою долю). При этом \(S\) не обязательно должно делиться на \(k + 1\): главное — купить билет, а между собой друзья уж как-нибудь договорятся.
Всего у Коли \(n\) друзей, при этом \(i\)-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше \(b_i\) (больше денег у него просто с собой нет) и не меньше \(a_i\) (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).
Так что может так получиться, что всех позвать не удастся. Ну и ладно. Для каждого своего друга Коля знает число \(f_i\) — количество веселья, который тот произведет, если его позвать.
Помогите Коле выбрать подмножество друзей, которых Коля должен позвать с собой, чтобы максимизировать суммарное веселье.
В первой строке входного файлы содержится два целых числа: \(n\) и \(S\) (\(1 \le n \le 100\,000\), \(0 \le S \le 10^9\)) — количество друзей Коли и стоимость билета. В следующих \(n\) строках содержится по три целых числа: в \(i\)-й из этих строк находятся числа \(a_i\), \(b_i\) и \(f_i\) (\(0 \le a_i \le b_i \le S\), \(0 \le f_i \le 10^9\)). Они означают, что \(i\)-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между \(a_i\) и \(b_i\), и он произведет \(f_i\) веселья.
В первой строке выходного файла выведите два числа: \(k\) (количество приглашенных на вечеринку друзей) и \(F\) (максимальное суммарное веселье, которое можно получить). Во второй строке выведите \(k\) чисел — номера друзей, которых нужно пригласить.
На одном из московских вокзалов билеты продают \(N\) касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.
Сначала вводится одно целое число \(N\) \((0 < N \le 10000)\).
В каждой из следующих \(N\) строк через пробел расположены 6 целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от 0 до 23, минуты и секунды — целые числа от 0 до 59), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.
Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с 10 ч 30 мин 30 с до 10 ч 35 мин 30 с, ежесуточно работает 300 секунд.
Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает — на следующий день.
Требуется вывести одно число — суммарное время за сутки (в секундах), на протяжении которого работают все \(N\) касс.
3 1 0 0 23 0 0 12 0 0 12 0 0 22 0 0 2 0 0
7200
2 9 30 0 14 0 0 14 15 0 21 0 0
0
2 14 0 0 18 0 0 10 0 0 14 0 1
1
На плоскости задано \(N\) прямоугольников с вершинами в точках с целыми координатами и сторонами, параллельными осям координат. Необходимо найти площадь их объединения.
В первой строке входного файла указано число \(N\) \((0 \le N \le 1500)\). В следующих \(N\) строках заданы по 4 целых числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего \((0 \le x_1 \le x_2 \le 10^9,\, 0 \le y_1 \le y_2 \le 10^9)\). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.
В выходной файл выведите единственное число — ответ на задачу.
3 1 1 3 5 5 2 7 4 2 4 6 7
23
2 0 0 2 2 1 3 2 4
5
На секретной военной базе работает N (1 ≤ N ≤ 10000) охранников. Сутки поделены на 10000 равных промежутков времени, и известно когда каждый из охранников приходит на дежурство и уходит с него. Например, если охранник приходит в 5, а уходит в 8, то значит, что он был в 6, 7 и 8-ой промежуток (а в 5-й нет!!!). В связи с уменьшением финансирования часть охранников решено было сократить.
Укажите, верно ли что для данного набора охранников, объект охраняется в любой момент времени хотя бы одним охранником и удаление любого из них приводит к появлению промежутка времени, когда объект не охраняется.
В первой строке входного файла записано натуральное число K (1 ≤ K ≤ 100) — количество тестов в файле. Каждый тест начинается с числа N, за которым следует N пар неотрицательных целых чисел A и B — время прихода на дежурство и ухода (0 ≤ A ≤ B ≤ 10000) соответствующего охранника.
Выведите K строк, где в M-ой строке находится слово Accepted, если M-ый набор охранников удовлетворяет описанным выше условиям. В противном случае выведите Wrong Answer.
2 3 0 3000 2500 7000 2700 10000 2 0 3000 2700 10000
Wrong Answer Accepted