[ROIR 2021] 分割数表 (Day 1)

Luogu
IDLGP9762
Time1000ms
Memory512MB
DifficultyP3
数学二分2021三分ROIR(俄罗斯)
有一个 $n\times m$ 的数表 $a$,$a_{i,j}=(i-1)\times m+j$。 现在将这个数表分成两个数表 $x,y$,使得 $\max\{\sum x,\sum y\}$ 最小。 形象化地来说,您可以确定一个 $i$,然后在数表的第 $i-1$ 列与第 $i$ 列间竖切一刀,或者在第 $i-1$ 行与第 $i$ 行间横切一刀,所得到的两个数表分为 $x,y$。 请构造一组方案。 ## Input **本题多组数据。** 第一行为一个整数 $t$。 接下来 $t$ 行,一行两个整数 $n,m$,表示本次询问的数表大小。 ## Output 对于每一个询问,输出一个字符 $c$ 和一个整数 $x$。 如果您想要竖切,$c$ 为 `V`,$x$ 为您确定的 $i$。 如果您想要横切,$c$ 为 `H`,$x$ 为您确定的 $i$。 如果有多解,请输出竖切的一种,如果还有多解,输出 $x$ 最小的一种。 [samples] ## Background **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day1 T2 [ Разбиение таблицы](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day1.pdf)**。 ## Note 【数据范围】: 对于所有子任务,有 $1\le t\le 10^5$,$1\le n,m\le 10^9$,$2\le n\times m\le 10^9$。 | 子任务编号 |数据范围 | 分值 | | :-: | :-: | :-: | |$1$|$t=1$,$n,m\le 100$| $20$ | |$2$|$t=1$,$n,m\le 2\times 10^3$| $14$ | |$3$|$t=1$,$n,m\le 10^7$| $15$ | |$4$| $t\le 10^3$,$n\times m\le10^4$ | $16$| |$5$|$n=1$| $15$ | |$6$|无特殊限制| $20$ |
Samples
Input #1
5
1 3
4 7
1 10
3 3
3 5
Output #1
V 3
V 5
V 8
H 3
V 4
API Response (JSON)
{
  "problem": {
    "name": "[ROIR 2021] 分割数表 (Day 1)",
    "description": {
      "content": "有一个 $n\\times m$ 的数表 $a$,$a_{i,j}=(i-1)\\times m+j$。 现在将这个数表分成两个数表 $x,y$,使得 $\\max\\{\\sum x,\\sum y\\}$ 最小。 形象化地来说,您可以确定一个 $i$,然后在数表的第 $i-1$ 列与第 $i$ 列间竖切一刀,或者在第 $i-1$ 行与第 $i$ 行间横切一刀,所得到的两个数表分为 $x,y$。 请构造",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9762"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个 $n\\times m$ 的数表 $a$,$a_{i,j}=(i-1)\\times m+j$。\n\n现在将这个数表分成两个数表 $x,y$,使得 $\\max\\{\\sum x,\\sum y\\}$ 最小。\n\n形象化地来说,您可以确定一个 $i$,然后在数表的第 $i-1$ 列与第 $i$ 列间竖切一刀,或者在第 $i-1$ 行与第 $i$ 行间横切一刀,所得到的两个数表分为 $x,y$。\n\n请构造...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments