Разбиение таблицы
(Время: 2 сек. Память: 16 Мб Сложность: 32%)
Рассмотрим таблицу из n строк и m столбцов, в клетки которой по строкам записаны числа от 1 до n×m. Сначала заполняется первая строка слева направо, затем вторая, и так далее. Другими словами, в клетку (r,c) записывается число (r-1)×m+c.
На рисунке приведен пример такой таблицы для n=3, m=5.
Требуется разделить таблицу одним вертикальным или горизонтальным разрезом, проходящим по сторонам клеток, так чтобы сумма чисел в получившихся частях таблицы отличалась как можно меньше. В этой задаче в одном тесте вам придётся ответить на несколько запросов об оптимальном разрезании таблицы.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число t — количество запросов (1 ≤ t ≤ 105). В каждой из следующих t строк записаны два числа n и m, разделенные пробелом (1 ≤ n,m ≤ 109, 2 ≤ n×m ≤ 109).
Выходные данные
В t строках выходного файла OUTPUT.TXT выведите ответы на запросы, по одному на строке.
Ответ на каждый запрос должен быть выведен в формате «D x», где D — это «V», если нужно резать по вертикали, «H» — если по горизонтали, а x — номер столбца или строки, перед которым надо сделать разрез. Строки пронумерованы от 1 до n, столбцы пронумерованы от 1 до m.
Если правильных ответов несколько, то надо вывести вариант с вертикальным разрезом, если он есть, а если и после этого вариантов несколько, то из вариантов с различными x следует выбрать тот, в котором x меньше.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5
1 3
4 7
1 10
3 3
3 5 | V 3
V 5
V 8
H 3
V 4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|