жадные алгоритмы

Два неориентированных графа G и H называются изоморфными , если:

• они имеют одинаковое количество вершин;
• существует такое однозначное соответствие между их вершинами, что любые две различные вершины графа G соединены ребром тогда и только тогда, когда соединены ребром соответствующие вершины графа H.

Например, следующие два графа изоморфны, хотя выглядят по-разному:


 

Возможным однозначным соответствием, показывающим, что эти два графа изоморфны, является {a-1, b-6, c-8, d-3, g-5, h-2, i-4, j-7}, хотя существуют и другие подобные соответствия.

Подграфом графа G называется граф, множества вершин и ребер которого являются подмножествами множеств вершин и ребер графа G. Заметьте, что граф G является также и своим подграфом. На рисунке показаны граф и один из его подграфов:

Говорят, что граф G содержит другой граф H , если существует хотя бы один подграф H ’ графа G , который изоморфен H . Следующий рисунок показывает граф G , который содержит граф H .



ЗАДАНИЕ

По двум заданным неориентированным графам G и H постройте подграф G’ графа G такой, что:

количество вершин в графах G и G’ одинаково;
H не содержится в G’ .
Естественно, может быть много подграфов графа G’ с перечисленными свойствами. Постройте подграф с как можно большим количеством ребер.

БАЗОВЫЙ АЛГОРИТМ

Возможно, наиболее простой стратегией при решении этой задачи будет следующая: рассматривать ребра графа G в порядке, в котором они представлены во входных данных, после чего пытаться добавлять ребра одно за другим в граф G’, проверяя на каждом шаге, входит ли граф H в граф G’ или нет. Правильная реализация этого жадного алгоритма наберет некоторое количество очков, хотя существуют гораздо лучшие стратегии.

ОГРАНИЧЕНИЯ

3 ≤ m ≤ 4    m – количество вершин в H.
3 ≤ n ≤ 1000    n – количество вершин в G .

ВВОД

Вы получите 10 тестов каждый со следующими данными:
 

Пример ввода

ОПИСАНИЕ

3 5 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0

СТРОКА 1: Содержит два целых числа, разделенных пробелом, соответственно m и n. СЛЕДУЮЩИЕ m СТРОК: Каждая строка содержит m целых чисел, разделенных пробелами, и представляет одну вершину из H в порядке 1, ..., m . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в H , и равняется 0 в противном случае. СЛЕДУЮЩИЕ n СТРОК : Каждая строка содержит n целых чисел, разделенных пробелами, и представляет одну вершину из G в порядке 1, ..., n . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в G , и равняется 0 в противном случае.

 

Заметьте, что за исключением строки 1, приведенные входные данные представляют собой матрицы смежности графов H и G .

ВЫВОД

Вы должны создать 10 выводов по одному на каждый входной. Каждый тест должен содержать следующие данные:

Пример вывода

ОПИСАНИЕ

#FILE forbidden K 5 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

СТРОКА 1: Заголовок файла. Заголовок файла должен содержать #FILE forbidden K где K – это число между 1 и 10, которое соответствует решенному входному файлу. СТРОКА 2: Содержит одно целое число : n . СЛЕДУЮЩИЕ n СТРОК : Каждая строка содержит n целых чисел, разделенных пробелом, и представляет одну вершину из G’ в порядке 1, ..., n . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в G’ , и равняется 0 в противном случае.

Заметьте, что за исключением строк 1 и 2, приведенные входные данные представляют собой матрицу смежности графа G’. Обратите внимание, что есть много вариантов ответа, и приведенный вариант является корректным, но не оптимальным.

Вася уже в десятом классе. После месяца ежедневных заруб в доту со своими товарищами, он начал замечать, что его оценки начали проседать. Исправлять их он, конечно же не собирается, но есть один нюанс...
Вместе с Васей в классе учится сын маминой подруги — Петя. Вася очень не любит его, потому что мама Васи дружит с мамой Пети и знает про него почти всё. В конце триместра у васиной мамы есть традиция садиться и сравнивать оценки Васи с оценками Пети. За каждый случай, когда у Васи оценка ниже, чем у Пети, мама выдаёт ему наряд вне очереди! — мыть весь день посуду, пропылесосить во всём доме, помыть окна или отвести/забрать младшую сестру из детского сада.
Конечно же, эта ситуация Васе не очень нравится, потому что в среднем Вася умнее Пети. Вася хочет минимизировать количество штрафных нарядов, поэтому он собирается перемешать оценки.
Помимо оценок в журнале встречается метка n. Она означает, что ученика на уроке не было. Если кого-то из учеников не было на уроке, то мама Васи не может сравнить успехи своего сына и сына своей подруги, поэтому штрафной наряд выписан быть не может
Помогите Васе перемешать свои оценки и n-ки так, чтобы получить как можно меньше штрафных нарядов. Если существует несколько решений, выведите любое.
В школе N различных предметов, и по каждому из них Вася должен перемешать оценки.
В каждом тесте первое число N — это количество предметов, за которые получены оценки в этом триместре. В следующих 2N строках находятся N блоков по 2 строки. В каждом блоке в первой строке находятся оценки Васи, а во второй — оценки Пети. Для каждого блока в новой строчке нужно вывести такую перестановку номеров оценок и меток n, что a_i означает, что Васина оценка под номером i должна занять позицию a_i.
В первом тесте N = 30. Оценка за этот тест: 30 баллов. За каждый предмет, за который получено больше штрафных нарядов, чем могло бы быть, снимается 1 балл. Проверка осуществляется в режиме online (результат виден сразу).
Во втором тесте N = 35. Оценка за этот тест: 70 баллов. За каждый предмет, за который получено больше штрафных нарядов, чем могло бы быть, снимается 2 балла. Во время тура проверяется, что по каждому предмету сдана корректная перестановка. Проверка правильности ответа осуществляется в режиме offline (результат виден после окончания тура).

Примеры

№	Входные данные	Выходные данные
1	3 5 4 4 3 4 4 5 5 4 5 5 4 n 3 4 n 4 n 4 n 4 1 3 2 4 3 2 1 5	5 1 2 4 3 1 2 3 4 3 4 2 1

В первом примере Вася получит 4 наряда вне очереди. Во втором примере ничего никуда переставлять не надо, потому что на единственном уроке, на котором присутствовали оба ученика, они получили по 4 балла. В третьем примере Вася переставит оценки вот так: 4, 2, 1, 3 и получит один наряд вне очереди

 

Компания ADM представила новый квантовый процессор. Благодаря нему очень быстро можно применять функцию «tripleswap» к некоторому массиву a.

tripleswap(i, j, k, x, y, z) — переставляет элемент, который стоит на позиции i на позицию x, элемент с позиции j на позицию y и элемент с позиции k на позицию z. При этом i, j, k, x, y и z — корректные индексы массива, множество {i,j,k} совпадает с множеством {x,y,z}, а также выполняется условие, что i, j, k различны между собой и x, y, z различны между собой.

Таким, образом, пусть есть массив, содержащий первую перестановку из пяти элементов [1,2,3,4,5]. Если применить к нему tripleswap(1, 5, 4, 5, 1, 4) получится массив [5,2,3,4,1]. При этом, выполнить tripleswap(1, 5, 4, 5, 2, 4) или tripleswap(1, 5, 1, 5, 1, 1) нельзя, так как такие наборы аргументов считаются некорректными.

Вас пригласили протестировать возможности нового процессора. Для первого теста вам дана перестановка из n чисел, нужно отсортировать ее по возрастанию при помощи функции tripleswap, вызвав данную функцию не более, чем n/2 раз (деление целочисленное, 5/2=2).

Входные данные

В первой строке дано одно натуральное число n — размер перестановки (3≤n≤100).

Во второй строке заданы n чисел a_i — элементы перестановки (1≤a_i≤n). Гарантируется, что все a_i попарно различны.

Выходные данные

В первой строке выведите одно число m — число вызов функции tripleswap, которые сортируют данную перестановку требуемым способом.

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

Если есть несколько решений, разрешается вывести любое.
 

Ввод	Вывод
5 1 2 3 4 5	0
5 5 4 3 2 1	2 2 4 5 4 5 2 1 2 5 5 1 2

Примечание
В первом тесте последовательность уже отсортирована, поэтому потребуется ноль вызовов данной функции. Во втором тесте изменение элементов массива будет выглядеть следующим образом: [5,4,3,2,1]⇒[5,1,3,4,2]⇒[1,2,3,4,5].