Имя входного файла: schedule.in
Имя выходного файла: schedule.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Имеется некоторое множество заданий и один исполнитель. На выполнение одного задания уходит единица времени. Задания можно выполнять начинаяс момента времени 0. У каждого задания есть две характеристики: d_i и w_i. Если задание не было выполнено к моменту времени d_i, взимается штраф в размере w_i. Требуется минимизировать суммарный штраф.
Первая строка входного файла содержит натуральное число n — количество заданий ( 1 ≤ n ≤ 100 000). Следующие n строк содержат по два натуральных числа, разделенных пробелом — d_i и w_i ( 0 ≤ d_i; w_i ≤ 10^9).
Выведите одно число — минимальный суммарный штраф.
schedule.in
2
1 1
1 2
schedule.out
1
Имя входного файла: destroy.in
Имя выходного файла: destroy.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64мегабайта
Дан связный взвешенный граф. Требуется уничтожить максимальное количество ребер, чтобы были выполнены следующие условия: суммарная стоимость уничтоженных ребер не превосходила s, оставшийся после уничтожения граф должен быть связен.
Первая строка входного файла содержит числа n и m — количество вершин и ребер в графе, и s — максимальную суммарную стоимость уничтоженных ребер ( 2 ≤ n ≤ 50 000, 1 ≤ m ≤ 100 000, 0 ≤ s ≤ 10^18 ). Следующие m строк описывают ребра — для каждого ребра указаны номера вершин, которые оно соединяет, истоимость уничтожения этого ребра (непревышает 10^18).
На первой строке выходного файла выведите максимальное количество ребер, которые можно уничтожить. На второй строке выведите их номера в порядке возрастания (ребра нумеруются с единицы в порядке, в котором они заданы во входном файле).
destroy.in
6 7 10
1 2 3
1 3 3
2 3 3
3 4 1
4 5 5
5 6 4
4 6 5
destroy.out
2
1 5
Имя входного файла: matching.in
Имя выходного файла: matching.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дан двудольный граф. Количество вершин в левой и правой доле совпадает и равно n. У каждой вершины левой доли есть вес, i-й вершине соответствует вес w_i. Вес паросочетания, ребрам которого инцидентны вершины левой доли a_1, a_2,..., a_k есть √∑i=1..k: w^2,a_i. Требуется найти паросочетание максимального веса.
Первая строка входного файла содержит натуральное число n — количество вершин в обеих долях ( 1 ≤ n ≤ 1000 ). Вторая строка входного файла содержит n целых чисел w_1, w_2,...; w_n ( 1 ≤ w_i ≤ 1000 ). Следующие n строк содержат описания ребер, инцидентных соответствующей вершине левой доли. Формат описания: количество ребер, затем номера вершин правой доли, разделенные пробелом. Суммарное количество ребер не превосходит 200000.
Выведите n чисел — для каждой вершины левой доли выведите номер вершины правой доли, с которой ее надо взять в паросочетание. Если вершина не входит в паросочетание, выведите 0.
matching.in
4
1 3 2 4
4 1 2 3 4
2 1 4
2 1 4
2 1 4
matching.out
2 1 0 4
Имявходного файла: check.in
Имявыходного файла: check.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дано некоторое семейтво множеств S ⊂ 2^X. Требуется проверить, может ли S быть семейством независимых множеств некоторого матроида.
Первая строка входного файла содержит два натуральных числа n и m — мощность множеств X и S соответственно ( 1 ≤ n ≤ 10 , 0 ≤ m ≤ 2n). Каждая из следующих m строк содержит описание элемента множества S. Формат описания: количество элементов в подмножестве, затем через пробел номера этих элементов. Элементы множества X занумерованы начиная с единицы.
Выведите «YES», если S может быть семейством независимых множеств некоторого матроида и «NO» иначе.
check.in
2 4
0
1 1
1 2
2 1 2
check.out
YES
check.in
2 3
0
1 1
2 1 2
check.out
NO
Имя входного файла: cycles.in Имя выходного файла: cycles.out Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Дано некоторое семейство множеств S ⊂ 2^X. Известно, что этом ножество циклов некоторого матроида. Кроме того, у каждого элемента множества X есть свой вес. Вес подможества X есть сумма весов элементов, принадлежащих ему. Требуется найти базу максимального веса.
Первая строка входного файла содержит два натуральных числа n и m — мощность множеств X и S соответственно (1 ≤ n ≤ 20). Вторая строка входного файла содержит n чисел w_1, w_2,..., w_n (1 ≤ w_i ≤ 1000). Здесь элементы множества X занумерованы начиная с единицы и w_i — вес i-го элемета множества X. Каждая из следующих m строк содержит описание элемента множества S. Формат описания: количество элементов в подмножестве, затем через пробел номера этих элементов.
Выведите одно число — вес максимальной базы.
cycles.in
3 1
10 20 30
3 1 3 2
cycles.out
50