Задача: E1 (2023). Bubble Sort
Перед вами поставили n стаканов, изначально в каждом из них может быть либо m, либо 0 разноцветных шариков.
Стаканы достаточно узки, поэтому шарики находятся один над другим и в любой момент времени достать можно только самый верхний. Иначе говоря, состояние стакана в любой момент времени представимо в виде массива чисел: 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
|
Ваш ответ: