---> 39 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 2 3 4 5 6 7 8 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Обратные задачи представляют собой быстро развивающуюся область информатики. В отличии от классической постановки задачи, где по заданным исходным данным $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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за $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$ чисел — номера друзей, которых нужно пригласить.

ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

На одном из московских вокзалов билеты продают $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
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано $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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На секретной военной базе работает 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

Страница: << 2 3 4 5 6 7 8 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест