Задача №115266. Нечестная игра
На клетчатой доске размером \(n \times m\), состоящей из \(n\) строк и \(m\) столбцов, в клетке \((r, c)\), то есть на пересечении \(r\)-й сверху строки и \(c\)-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.
Каждый ход устроен следующим образом.
- Компьютер называет целое число \(k > 0\).
- Вы ровно \(k\) раз некоторым образом выбираете одну из еще не удаленных клеток, соседних по стороне (имеющих общую сторону) с той, в которой фишка находится в текущий момент, и перемещаете фишку в эту клетку. Вы можете перемещать фишку на клетку, в которой она уже была. Если не существует еще не удаленных клеток, соседних по стороне с текущей, перемещение не производится.
- Компьютер называет координаты \((i, j)\) произвольной еще не удаленной клетки поля, после чего она сразу же удаляется.
Если компьютер удаляет клетку, на которой находится фишка, игра заканчивается вашей победой. Ваша цель — победить как можно раньше. При этом вы не сообщаете компьютеру свои перемещения, поэтому можете играть нечестно: вместо реального перемещения фишки по полю вы можете следить за всеми возможными ее положениями. Иными словами, если в какой-то момент при удалении клетки \((i, j)\) существует последовательность перемещений фишки, при которой в данный момент фишка находится в точности в клетке \((i, j)\), вы можете сообщить компьютеру, что игра завершена, и вы победили.
Разумеется, компьютер следит за соблюдением правил, поэтому если вы сообщаете ему о своей победе при удалении клетки, на которой фишка не могла в этот момент находиться, вы автоматически проигрываете.
Определите как можно меньший номер хода, после которого вы можете сообщить комьютеру о своей победе, то есть после которого фишка могла оказаться на удаляемой клетке. Чем ближе ваш ответ к минимальному возможному, тем больше баллов вы получите.
В единственной строке ввода даны четыре целых числа \(n\), \(m\), \(r\) и \(c\) — размеры доски и координаты изначального расположения фишки (\(1 \le r \le n \le 1000\); \(1 \le c \le m \le 1000\)).
Во второй строке ввода дано максимальное количество баллов, которое можно получить за соответствующую группу тестов. Ваше решение это значение может игнорировать.
В следующих \(n \cdot m\) строках даны ходы, которые последовательно собирается сделать компьютер. Описание \(t\)-го хода задается тремя целыми числами \(k_t\), \(i_t\) и \(j_t\) — количеством перемещений фишки, которые вам понадобится совершить, и координатами клетки поля, которую после этого требуется удалить (\(1 \le k_t \le 10^9\); \(1 \le i_t \le n\); \(1 \le j_t \le m\)).
Гарантируется, что все удаляемые клетки различны, то есть никакая клетка не удаляется дважды.
Выведите одно целое число от \(1\) до \(n \cdot m\) — номер хода, после которого вы сообщите компьютеру о своей победе.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач пройдены с положительным вердиктом.
То есть, если вы проигрываете игру на каком-либо тесте группы, вы получаете вердикт WA за соответствующий тест и \(0\) баллов за всю группу. Иначе, если \(R(\mathtt{group})\) — максимальное число баллов за группу, а \(j(\mathtt{test})\) и \(p(\mathtt{test})\) — ответы на тест программы жюри и вашей программы, соответственно, вы получаете за группу \(\)\left\lfloor R(\mathtt{group}) \cdot \min\limits_{\mathtt{test} \in \mathtt{group}} \frac{j(\mathtt{test})}{p(\mathtt{test})} \right\rfloor \text{ баллов.}\(\)
Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 7 | \(k_1 = n + m\) | полная | |
| 2 | 6 | \(k_t = 1\) для всех \(t\) | первая ошибка | |
| 3 | 10 | ходы компьютера случайны и равновероятны | 0 | первая ошибка |
| 4 | 14 | \((i_t, j_t)\) и \((i_{t+1}, j_{t+1})\) имеют общую сторону для всех \(t\) | 0 | первая ошибка |
| 5 | 11 | \(k_t \le 2\) для всех \(t\) | 2 | первая ошибка |
| 6 | 17 | \(n = 1\) | полная | |
| 7 | 9 | \(n, m \le 40\) | 0 | первая ошибка |
| 8 | 9 | \(r = c = 1\) | полная | |
| 9 | 17 | без дополнительных ограничений | 0 – 8 | первая ошибка |
В первом примере можно, например, первым ходом передвинуть фишку из \((1, 1)\) в \((1, 2)\), а вторым — из \((1, 2)\) в \((2, 2)\) и затем в \((2, 1)\), тем самым поместив ее на удаляемую клетку.
2 2 1 1 0 1 1 1 2 2 1 3 2 2 4 1 2
2
3 3 2 2 0 1 2 2 1 1 2 1 1 1 1 2 1 1 3 1 1 3 2 1 3 3 1 2 3 1 1 3
9