electicode
ГлавнаяКурсыРесурсыЗадачиНациональная олимпиадаСоревнованияТаблица лидеров
...

Книжная полка

Ограничение времени: 1000msОграничение памяти: 256MB
Все решения

Описание задачи

Каримжон работает в Национальной библиотеке. В секции, где работает Каримжон, есть большой книжный стеллаж размера n×mn \times mn×m, где строки пронумерованы от 000 до n−1n-1n−1, а столбцы — от 000 до m−1m-1m−1.

Ячейка (i,j)(i, j)(i,j) стеллажа содержит книгу с номером a[i][j]a[i][j]a[i][j]. Все номера книг на стеллаже различны.

Каримжон может выполнять следующие две операции:

  • Перестановка строк: Для каждой строки переставить книги в этой строке в любом порядке. Порядок можно выбирать независимо для каждой строки.
  • Перестановка столбцов: Для каждого столбца переставить книги в этом столбце в любом порядке. Порядок можно выбирать независимо для каждого столбца.

Каримжон хочет отсортировать стеллаж. В отсортированном стеллаже строка 000 содержит все книги с номерами от 000 до m−1m-1m−1 в возрастающем порядке, строка 111 содержит все книги с номерами от mmm до 2m−12m-12m−1 в возрастающем порядке, и так далее. То есть для всех и должно выполняться условие .

Пусть RRR — минимальное число операций, необходимое для сортировки стеллажа. Вам также дано число TTT, где 1≤T≤21 \leq T \leq 21≤T≤2.

Если T=1T = 1T=1, вам нужно только найти минимальное число операций RRR.

Если T=2T = 2T=2, вам нужно найти RRR и также вывести последовательность операций, которая его достигает.

Формат ввода

Первая строка содержит три целых числа nnn, mmm и TTT.

Следующие nnn строк содержат по mmm целых чисел --- элементы a[i][0],a[i][1],…,a[i][m−1]a[i][0], a[i][1], \ldots, a[i][m-1]a[i][0],a[i][1],…,a[i][m−1].

Ограничения:

  • 1≤n,m≤1001 \leq n, m \leq 1001≤n,m≤100
  • 1≤T≤21 \leq T \leq 21≤T≤2
  • 0≤a[i][j]≤n⋅m−10 \leq a[i][j] \leq n \cdot m - 10≤a[

Формат вывода

Если T=1T = 1T=1, выведите одно целое число RRR --- минимальное число операций.

Если T=2T = 2T=2, выведите операции по порядку. Для каждой операции выведите строку, содержащую либо row, либо col, указывающую, является ли это перестановкой строк или перестановкой столбцов. Затем выведите nnn строк, каждая из которых содержит mmm целых чисел --- состояние стеллажа после применения этой операции. Наконец, в последней строке выведите RRR --- общее число выполненных операций.

Каждая перестановка строк должна только переставлять элементы внутри каждой строки (мультимножество элементов в каждой строке должно оставаться тем же по сравнению с состоянием до этой операции). Каждая перестановка столбцов должна только переставлять элементы внутри каждого столбца (мультимножество элементов в каждом столбце должно оставаться тем же по сравнению с состоянием до этой операции).

После всех операций стеллаж должен быть отсортирован, т.е. a[i][j]=i⋅m+ja[i][j] = i \cdot m + ja[i][j]=i⋅m+j для всех i,ji, ji,j.

Число операций должно быть равно RRR, минимально возможному.

Оценивание

ПодзадачаДополнительные ограниченияБаллыТребуемая подзадача
000Тесты из примера000-
111n,m≤3n, m \leq 3n,m

Примеры

Пример 1
Ввод
2 2 2
1 0
3 2
Вывод
row
0 1
2 3
1
Объяснение

Здесь T=2T = 2T=2. Минимальное количество операций равно R=1R = 1R=1. Мы выполняем одну перестановку строк: в строке 000 мы переставляем [1,0][1, 0][1, в ; в строке мы переставляем в .

© 2026 Electicode. All rights reserved.

0≤i≤n−10 \leq i \leq n-1
0≤i≤n−1
0≤j≤m−10 \leq j \leq m-10≤j≤m−1
a[i][j]=i⋅m+ja[i][j] = i \cdot m + ja[i][j]=i⋅m+j
i
]
[
j
]
≤
n⋅
m−
1
  • Все элементы матрицы aaa различны.
    • ≤
    3
    151515
    -
    222T=1T = 1T=1151515-
    333Гарантируется, что R≤2R \leq 2R≤2101010-
    444n≤3n \leq 3n≤3, m≤15m \leq 15m≤15151515111
    555n,m≤15n, m \leq 15n,m≤15181818000, 111, 444
    666Без дополнительных ограничений272727000, 111, 222, 333, 444, 555
    0
    ]
    [0,1][0, 1][0,1]
    111
    [3,2][3, 2][3,2]
    [2,3][2, 3][2,3]
    Пример 2
    Ввод
    2 3 1
0 4 2
5 1 3
    Вывод
    2
    Объяснение

    Здесь T=1T = 1T=1, поэтому нам нужно вывести только R=2R = 2R=2.

    Пример 3
    Ввод
    5 3 2
10 9 11
14 5 12
1 4 7
3 8 13
2 6 0
    Вывод
    row
11 9 10
12 14 5
4 7 1
8 3 13
0 2 6
col
0 2 1
4 3 5
8 7 6
11 9 10
12 14 13
row
0 1 2
3 4 5
6 7 8
9 10 11
12 13 14
3
    Объяснение

    Минимум — R=3R = 3R=3. Мы выполняем: перестановку строк, затем перестановку столбцов, затем перестановку строк. После всех трёх операций книжная полка отсортирована.