Задача A. Паросочетание

Автор:std.alg   Ограничение времени:2 сек
Входной файл:pairs.in   Ограничение памяти:256 Мб
Выходной файл:pairs.out  

Условие

Двудольным графом называется граф (V,E), E ⊂ V × V такой, что его множество вершин V можно разбить на два подмножества A и B, для которых ∀ (e1,e2) ∈ E e1 ∈ A, e2 ∈ B и A, B ⊂ E, A ∩ B = varnothing.

Паросочетанием в двудольном графе называется любой его набор несмежных ребер, то есть такой набор S ⊂ E, что для любых двух ребер e1 = (u1, v1), e2 = (u2, v2) из S выполнено u1 ≠ u2 и v1 ≠ v2.

Ваша задача — найти максимальное паросочтание в двудольном графе, то есть паросочетание с максимально возможным числом ребер.

Формат входного файла

В первой строке записаны два целых числа n и m (1≤ n, m ≤ 250)  — число вершин в A и число вершин в B.

Далее следуют n строк с описаниями ребер. i-я вершина из A описана в i + 1-й строке файла. Каждая из этих строк содержит номера вершин из B, соединенных с i-й вершиной A. Вершины в A и B нумеруются независимо (с единицы). Список завершается числом 0.

Формат выходного файла

Первая строка выходного файла должна содержать одно целое число l — количество ребер в максимальном паросочетании. Далее должны следовать l строк, в каждой из которых должны быть два целых числа uj и vj — концы ребер паросочетания в A и B, соотвественно.

Ограничения

Примеры тестов

Входной файл (pairs.in) Выходной файл (pairs.out)
1
2 2
1 2 0
2 0
2
1 1
2 2

Задача C. Слово из кубиков

Автор:A. Klenin   Ограничение времени:8 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Имеется N кубиков, на гранях которых написаны буквы. Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов, и если да, то вывести номера использованных кубиков. При этом каждый кубик можно использовать только один раз. Если решений несколько, выдать любое из них.

Формат входного файла

В первой строке входного файла содержится количество кубиков N. Во второй строке — слово, в следующих N строках — по шесть символов без разделителей, определяющих буквы на гранях кубиков. (Порядок букв не имеет значения).

Формат выходного файла

Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N, задающих номера кубиков для каждой буквы слова, начиная с первой. Если решения нет, выходной файл должен содержать единственное число 0.

Ограничения

1 ≤ N, K ≤ 12.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
2 5 3 4

Problem D. Bipartite graph

Author:StdAlg (adapted by T. Chistyakov, A. Klenin)   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

For a given undirected graph with N vertices and M edges you need to figure out whether the graph is bipartite or no.

NOTE. A graph is called bipartite if it's possible to split its vertices into two non-empty sets so that there is no edges between any two vertices from the same set.

Input file format

Input file contains integers N M, then M pairs of integers ai bi describing the edges of the graph.

Output file format

Output BIPARTITE if the graph is bipartite or NO if it is not.

Constraints

1 ≤ N ≤ 100000, 0 ≤ M ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2
1 2  1 3
BIPARTITE
2
4 6
1 2  2 3  3 4  4 1  1 3  2 4
NO

Задача E. Прямые

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Даны n прямых на плоскости. Ваша задача — выбрать максимально возможное подмножество этих прямых так, чтобы среди выбранных прямых не было одинаковых прямых, параллельных прямых, прямых имеющих один и тот же y пересечения с прямой x = 0.

Формат входного файла

На первой строке количество тестов T, далее идёт описание T тестов. Первая строка теста содержит количество прямых n. Каждая из следующих n строк содержит по три целых числа Ai, Bi и Ci, описывающих прямую, как множество точек (x, y), для которых Ai x + Bi y + Ci = 0. Сумма n по всем тестам не превосходит 3000.

Формат выходного файла

Для каждого теста на одной строке выведите k — максимальный размер подмножества прямых. На следующей строке k целых чисел от 1 до n — номера выбранных прямых в произвольном порядке. Прямые нумеруются от 1 в том порядке, в котором даны в описании теста. Если существует несколько оптимальных решений, выведите любое одно.

Ограничения

1 ≤ n ≤ 3000

 − 109 ≤ A, B, C ≤ 109, A2 + B2 > 0

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
2
1 1 0
1 1 1
2
-1 1 1
-2 1 1
1
1
1
1

Задача F. Минимальное контролирующее множество

Автор:std.alg   Ограничение времени:2 сек
Входной файл:minimal.in   Ограничение памяти:256 Мб
Выходной файл:minimal.out  

Условие

Требуется построить в двудольном графе минимальное контролирующее множество, если дано максимальное паросочетание.

Формат входного файла

В первой строке файла даны два числа m и n (1≤ m, n≤ 4 000) — размеры долей. Каждая из следующих m строк содержит список ребер, выходящих из соответствующей вершины первой доли. Этот список начинается с числа Ki (0≤ Ki≤ n) — количества ребер, после которого записаны вершины второй доли, соединенные с данной вершиной первой доли, в произвольном порядке. Сумма всех Ki во входном файле не превосходит 500 000.

Последняя строка файла содержит некоторое максимальное паросочетание в этом графе — m чисел 0≤ Li≤ n — соответствующая i-й вершине первой доли вершина второй доли, или 0, если i-я вершина первой доли не входит в паросочетание.

Формат выходного файла

Первая строка содержит размер минимального контролирующего множества.

Вторая строка содержит количество вершин первой доли S, после которого записаны S чисел — номера вершин первой доли, входящих в контролирующее множество, в возрастающем порядке.

Третья строка содержит описание вершин второй доли в аналогичном формате.

Ограничения

Примеры тестов

Входной файл (minimal.in) Выходной файл (minimal.out)
1
3 2
2 1 2
1 2
1 2
1 2 0
2
1 1
1 2

Задача G. Мошенники

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Студенты придумали N тем для курсовых, название каждой состоит из двух слов из заглавных букв английского алфавита. Среди студентов есть читеры, которые вместо того, чтобы придумывать собственные названия, взяли оба слова из уже придуманных их коллегами тем. При этом в качестве первого слова они взяли первое слово одной из тем, а в качестве второго второе. Вам даны все N названий в произвольном порядке, определите максимальное число читеров среди студентов.

Формат входного файла

Первая строка содержит число тестов T. Каждый тест содержит N и N пар слов — названия тем. Все названия различны.

Формат выходного файла

Выведите максимальное число читеров. Формат вывода смотрите в примере.

Ограничения

1 ≤ T ≤ 100, 1 ≤ N ≤ 1000, длины слов от 1 до 20.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
3
HYDROCARBON COMBUSTION
QUAIL BEHAVIOR
QUAIL COMBUSTION
3
CODE JAM
SPACE JAM
PEARL JAM
2
INTERGALACTIC PLANETARY
PLANETARY INTERGALACTIC
Case #1: 1
Case #2: 0
Case #3: 0

0.395s 0.016s 23