Задача №114536. Разбиение таблицы
Рассмотрим таблицу из \(n\) строк и \(m\) столбцов, в клетки которой по строкам записаны числа от \(1\) до \(n \cdot m\). Сначала заполняется первая строка слева направо, затем вторая, и так далее. Другими словами в клетку \((r, c)\) записано число \((r - 1) \cdot m + c\).
На рисунке приведен пример такой таблицы для \(n = 3\), \(m = 5\).
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 |
Требуется разделить таблицу одним вертикальным или горизонтальным разрезом, проходящим по сторонам клеток, так чтобы сумма чисел в получившихся частях таблицы отличалась как можно меньше. В этой задаче в одном тесте вам придётся ответить на несколько запросов об оптимальном разрезании таблицы.
В первой строке ввода задано целое число \(t\) — количество запросов (\(1 \le t \le 10^5\)).
В следующих \(t\) строках заданы по два числа \(n\), \(m\) (\(1 \le n, m \le 10^9\), \(2 \le n \cdot m \le 10^9\)).
В \(t\) строках выведите ответы на запросы, по одному на строке.
Ответ на каждый запрос должен быть выведен в формате « D \(x\) », где D — это « V », если нужно резать по вертикали, « H » — если по горизонтали, а \(x\) — номер столбца или строки, перед которым надо сделать разрез. Строки пронумерованы от \(1\) до \(n\), столбцы пронумерованы от \(1\) до \(m\).
Если правильных ответов несколько, то надо вывести вариант с вертикальным разрезом, если он есть, а если и после этого вариантов несколько, то из вариантов с различными \(x\) следует выбрать тот, в котором \(x\) меньше.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 20 | \(t = 1\), \(1 \le n, m \le 100\) | полная | |
| 2 | 14 | \(t = 1\), \(1 \le n, m \le 2\,000\) | 1 | первая ошибка |
| 3 | 15 | \(t = 1\), \(1 \le n, m \le 10^7\) | 1, 2 | первая ошибка |
| 4 | 16 | \(1 \le t \le 1\,000\), \(1 \le n \times m \le 10\,000\) | 1 | первая ошибка |
| 5 | 15 | \(1 \le t \le 100\,000\), \(n = 1\), \(1 \le m \le 10^9\) | первая ошибка | |
| 6 | 20 | \(1 \le t \le 100\,000\), \(1 \le n, m \le 10^9\) | 1–5 | первая ошибка |
5 1 3 4 7 1 10 3 3 3 5
V 3 V 5 V 8 H 3 V 4