Перед вами поставили
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
|