Решение задачи Игра с фишками с Codeforces
Без пояснения   Просмотров: 167
У Пети есть прямоугольная доска размера n×m. Изначально на доске размещено k фишек, i-я из них находится в клетке, на пересечении sxi-й строки и syi-го столбца.
За одно действие Петя может сдвинуть все фишки влево, вправо, вниз или вверх на 1 ячейку.
Если фишка была в клетке (x,y), то после операции:
влево, ее координаты будут (x,y−1);
вправо, ее координаты будут (x,y+1);
вниз, ее координаты будут (x+1,y);
вверх, ее координаты будут (x−1,y).
Если фишка находится у стенки доски, и действие, выбранное Петей, двигает ее в направлении стены, то фишка остается на своей текущей позиции.
Обратите внимание, что несколько фишек могут располагаться в одной и той же клетке.
Для каждой фишки Петя выбрал позицию, в которой она должна побывать. Обратите внимание, что фишка не обязательно заканчивает в этой позиции.
Так как у Пети не очень много свободного времени, он готов сделать не более 2nm действий, описанных выше.
Вам предстоит выяснить, какие действия должен делать Петя, чтобы все фишки побывали хотя бы раз в выбранных для них клетках. Или определить, что за 2nm действий выполнить это невозможно.
За одно действие Петя может сдвинуть все фишки влево, вправо, вниз или вверх на 1 ячейку.
Если фишка была в клетке (x,y), то после операции:
влево, ее координаты будут (x,y−1);
вправо, ее координаты будут (x,y+1);
вниз, ее координаты будут (x+1,y);
вверх, ее координаты будут (x−1,y).
Если фишка находится у стенки доски, и действие, выбранное Петей, двигает ее в направлении стены, то фишка остается на своей текущей позиции.
Обратите внимание, что несколько фишек могут располагаться в одной и той же клетке.
Для каждой фишки Петя выбрал позицию, в которой она должна побывать. Обратите внимание, что фишка не обязательно заканчивает в этой позиции.
Так как у Пети не очень много свободного времени, он готов сделать не более 2nm действий, описанных выше.
Вам предстоит выяснить, какие действия должен делать Петя, чтобы все фишки побывали хотя бы раз в выбранных для них клетках. Или определить, что за 2nm действий выполнить это невозможно.