题目背景
译自 ROIR 2021 Day1 T2 Разбиение таблицы。
题目描述
有一个 n×m 的数表 a,ai,j=(i−1)×m+j。
现在将这个数表分成两个数表 x,y,使得 max{∑x,∑y} 最小。
形象化地来说,您可以确定一个 i,然后在数表的第 i−1 列与第 i 列间竖切一刀,或者在第 i−1 行与第 i 行间横切一刀,所得到的两个数表分为 x,y。
请构造一组方案。
输入格式
本题多组数据。
第一行为一个整数 t。
接下来 t 行,一行两个整数 n,m,表示本次询问的数表大小。
输出格式
对于每一个询问,输出一个字符 c 和一个整数 x。
如果您想要竖切,c 为 V
,x 为您确定的 i。
如果您想要横切,c 为 H
,x 为您确定的 i。
如果有多解,请输出竖切的一种,如果还有多解,输出 x 最小的一种。
提示
【数据范围】:
对于所有子任务,有 1≤t≤105,1≤n,m≤109,2≤n×m≤109。
子任务编号 |
数据范围 |
分值 |
1 |
t=1,n,m≤100 |
20 |
2 |
t=1,n,m≤2×103 |
14 |
3 |
t=1,n,m≤107 |
15 |
4 |
t≤103,n×m≤104 |
16 |
5 |
n=1 |
15 |
6 |
无特殊限制 |
20 |