Олимпиадный тренинг

Задача . E1 (2023). Bubble Sort


Задача

Темы:
Перед вами поставили n стаканов, изначально в каждом из них может быть либо m, либо разноцветных шариков.
Стаканы достаточно узки, поэтому шарики находятся один над другим и в любой момент времени достать можно только самый верхний. Иначе говоря, состояние стакана в любой момент времени представимо в виде массива чисел: a1, ..., at, где ai это цвет i-го шарика в стакане (нумерация начинается снизу).
Ваша задача - сделать так, чтобы шарики одного цвета оказались в одном стакане.
Пусть вы хотите переложить верхний шар из стакана i в стакан j. Вы можете это сделать только в случае, если выполнено одно из двух условий:
  • Стакан j пустой.
  • В стакане j сейчас ≤ m-1 шар, и цвет верхнего шара j-го стакана совпадает с цветом верхнего шара i-го стакана.
В первой строке входного файла указано число t - количество наборов входных данных в файле
Описание каждого набора начинается со строки, содержащей числа n и m количество стаканов и максимльно возможное количество шариков в одном стакане соответственно.
В последующих n строках указано содержание стаканов в формате: Сначала указано число ci - количество элементов в текущем стакане, после чего указаны ci чисел - цвета шариков в стакане, в порядке от самого нижнего до самого верхнего. Выведите t решений для наборов входных данных в следующем формате:
В первой строке каждого решения набора данных выведите число k - количество действий для сортировки в Вашем решении. В следующих k строках выведите сами действия: по два числа (xi, yi) операция перекладывания верхнего шара из стакана xi в стакан yi.
Оценка решения вычисляется по следующей формуле:
Введем функцию \(f(solution) = \sum\limits_{i=1}^n cnt_i^2\). Здесь cnti - количество различных элементов в итоговом стакане.
Введем функцию \(g(solution) =\frac{m\sqrt{n-\#empty}-{\sqrt{f(solution)-n+\#empty}}}{m\sqrt{n-\#empty}} \), где #empty - количество пустых стаканов.
Оценкой за решение одного набора входных данных будет величина 10·(g(solution)/g(jury_solution))3, jury_solution - это лучшее решение среди всех участников и решения жюри.
В этой задаче t = 3. Оценка за этот тест: 30 баллов. Баллы начисляются только в случае, если все выведенные ходы во всех тестах можно сделать.

Примеры
Входные данные Выходные данные
1
1
4 3
3 1 2 3
3 2 2 1
3 3 3 1
0
5
2 4
3 4
1 3
1 2
1 4

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя