#P13821. [wtf2019]Distinct Boxes

    ID: 13022 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS二分答案凸包二分查找二分第 k 小等差数列求和

[wtf2019]Distinct Boxes

题目描述

すぬけ君有 RR 个红球和 BB 个蓝球。他要把这些球分到 KK 个箱子里。此时,要求每个箱子都不能为空,并且任意两个箱子的内容不能完全相同。请你求出 KK 的最大可能值。

更形式化地说,给箱子编号 11 到 KK,设第 ii 个箱子中有 rir_i 个红球和 bib_i 个蓝球,需要满足以下条件:

  • 对于每个 ii(1≤i≤K1 \leq i \leq K),有 ri>0r_i > 0 或 bi>0b_i > 0。
  • 对于每一对 i,ji, j(1≤i<j≤K1 \leq i < j \leq K),有 ri≠rjr_i \neq r_j 或 bi≠bjb_i \neq b_j。
  • ∑ri=R\sum r_i = R 且 ∑bi=B\sum b_i = B(所有球都必须放入箱子中,不能有剩余)。

输入格式

输入从标准输入读入,格式如下:

RR BB

输出格式

输出 KK 的最大可能值。

输入输出样例 #1

输入 #1

8 3

输出 #1

5

说明/提示

限制条件

  • 1≤R,B≤1091 \leq R, B \leq 10^{9}

样例说明 1

下图展示了一种可以实现 K=5K = 5 的方法。

由 ChatGPT 4.1 翻译