Задача 2. Разбиение таблицы

Автор:Даниил Орешников   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Рассмотрим таблицу из n строк и m столбцов, в клетки которой по строкам записаны числа от 1 до n ⋅ m. Сначала заполняется первая строка слева направо, затем вторая, и так далее. Другими словами в клетку (r, c) записано число (r − 1) ⋅ m + c.

На рисунке приведен пример такой таблицы для n = 3, m = 5.

12345
678910
1112131415

Требуется разделить таблицу одним вертикальным или горизонтальным разрезом, проходящим по сторонам клеток, так чтобы сумма чисел в получившихся частях таблицы отличалась как можно меньше. В этой задаче в одном тесте вам придётся ответить на несколько запросов об оптимальном разрезании таблицы.

Формат входных данных

В первой строке ввода задано целое число t — количество запросов.

В следующих t строках заданы по два целых числа n, m.

Формат выходных данных

В t строках выведите ответы на запросы, по одному на строке.

Ответ на каждый запрос должен быть выведен в формате D x, где D — это "V", если нужно резать по вертикали, "H" — если по горизонтали, а x — номер столбца или строки, перед которым надо сделать разрез. Строки пронумерованы от 1 до n, столбцы пронумерованы от 1 до m.

Если правильных ответов несколько, то надо вывести вариант с вертикальным разрезом, если он есть, а если и после этого вариантов несколько, то из вариантов с различными x следует выбрать тот, в котором x меньше.

Ограничения

1 ≤ t ≤ 105, (1 ≤ n, m ≤ 109, 2 ≤ n ⋅ m ≤ 109)

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
120t = 1, 1 ≤ n, m ≤ 100полная
214t = 1, 1 ≤ n, m ≤ 2 0001первая ошибка
315t = 1, 1 ≤ n, m ≤ 1071, 2первая ошибка
4161 ≤ t ≤ 1 000, 1 ≤ n × m ≤ 10 0001первая ошибка
5151 ≤ t ≤ 100 000, n = 1, 1 ≤ m ≤ 109первая ошибка
6201 ≤ t ≤ 100 000, 1 ≤ n, m ≤ 1091 — 5первая ошибка

Примеры тестов

Стандартный вход Стандартный выход
1
5
1 3
4 7
1 10
3 3
3 5
V 3
V 5
V 8
H 3
V 4

Разбор

Подзадача 1

Переберем линию разделения. Затем за n ⋅ m посчитаем сумму в разделенной таблице. Выберем лучший разрез. В сумме решение работает за n ⋅ m ⋅ (n + m).

Подзадача 2

Заметим, что при перемещении линии разреза на 1 в каждой из половин добавляется или удаляется только O(n) или O(m) клеток. Значит можно перебрать все варианты за O(nm).

Подзадачи 3 и 4

Зафиксируем какой-нибудь разрез по вертикали перед столбцом k, посчитаем сумму в полученном прямоугольнике, используя сумму арифметической прогрессии:

a1 + a2 + a3 + …  + ax = (a1 + ax)2 ⋅ x

Применяя, получаем: 1 + 2 + …  + k + (m + 1) + (m + 2) + …  + (m + k) + …  + (m ⋅ (n − 1) + 1) + (m ⋅ (n − 1) + 2) + …  + (m ⋅ (n − 1) + k) = 

 = 1 + k2 ⋅ k + (m + 1) + (m + k))2 ⋅ k + …  + ((m ⋅ (n − 1) + 1) + (m ⋅ (n − 1) + k)2 ⋅ k

Полученная сумма также является арифметической прогрессией с шагом m ⋅ k, значит она равна:

1 + k2 ⋅ k + ((m ⋅ (n − 1) + 1) + (m ⋅ (n − 1) + k)2 ⋅ k2 ⋅ n

Сумму в горизонтальном разрезе найдем по более простой формуле:

1 + 2 + …  + m + (m + 1) + (m + 2) + …  + (m + m) + …  + (m ⋅ (k − 1) + 1) + (m ⋅ (k − 1) + 2) + …  + (m ⋅ (k − 1) + m)

1 + m ⋅ k2 ⋅ mk

Таким образом, за O(1) можно посчитать сумму при фиксированном разрезе, а значит, можно найти лучший разрез за (n + m).

Подзадача 5

Здесь арифметическая прогрессия одномерная, и надо найти такое k, чтобы

1 + k2 ⋅ k ≈ 1 + m4 ⋅ m

Решение 1

Упрощая, получим квадратное уравнение на k, и найдем лучшее k за O(1). Из-за округлений возможна погрешность, поэтому нужно перебрать ответ в диапазоне ± 1.

Решение 2

Можно найти лучшее k, используя двоичный поиск (сумма первых k значений возрастает при увеличении k).

Подзадача 6

Совместим идеи в подзадачах 4 и 5: Посчитаем сумму при фиксированной границе раздела:

1 + k2 ⋅ k + ((m ⋅ (n − 1) + 1) + (m ⋅ (n − 1) + k)2 ⋅ k2 ⋅ n ≈ 1 + n ⋅ m4 ⋅ nm

Решение 1 за O(1) на запрос

Упрощая, получим квадратное уравнение на k, и найдем лучшее k с точностью до ± 1, так как знак приблизительно равно.

Решение 2 за log2max(n, m) на запрос

Можно найти лучшее k, используя двоичный поиск, так как значение слева возрастает при увеличении k.


0.107s 0.018s 13