Решение задачи "Получи перестановку" с Codeforces

Без пояснения   Просмотров: 12


Вам задана прямоугольная матрица размера n×m, состоящая из целых чисел от 1 до 2⋅105. За один ход вы можете:

выбрать любой элемент матрицы и изменить его значение на любое целое число от 1 до n⋅m, включительно;
взять любой столбец и сдвинуть его на одну клетку вверх циклически (смотрите пример такого циклического сдвига ниже).
Циклический сдвиг — это операция, в которой выбирается некоторое j (1≤j≤m) и присваивается a1,j:=a2,j,a2,j:=a3,j,…,an,j:=a1,j одновременно.

Пример циклического сдвига первого столбца
Вы хотите определить минимальное количество шагов, за которое можно привести матрицу к подобному виду:


Другими словами, ваша цель — получить матрицу, в которой a1,1=1,a1,2=2,…,a1,m=m,a2,1=m+1,a2,2=m+2,…,an,m=n⋅m (i.e. ai,j=(i−1)⋅m+j) за минимальное число шагов.

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться