시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 3 | 3 | 3 | 100.000% |
Рассмотрим таблицу из $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$ --- количеcтво запросов ($1 \le t \le 10^5$).
В следующих $t$ строках заданы по два числа $n$, $m$ ($1 \le n, m \le 10^9$, $2 \le n \times 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$ |
3 | 15 | $t = 1$, $1 \le n, m \le 10^7$ |
4 | 16 | $1 \le t \le 1\,000$, $1 \le n \times m \le 10\,000$ |
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$ |
5 1 3 4 7 1 10 3 3 3 5
V 3 V 5 V 8 H 3 V 4
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2021 2번