#CF2266F. MEX Replacement
MEX Replacement
题目描述
给你一个以压缩形式表示的非负整数多重集。即,对于多重集中的每个值 ,你知道它的出现次数 。
在一次操作中,你可以选择当前多重集中任意非空的元素集合,移除所有被选中的元素,并插入一个等于它们的 的元素。
你可以执行操作任意次数,包括零次。
求在任意时刻多重集中可能出现的最大整数。
一个整数集合 的最小排除值(MEX)是不在该集合中出现的最小非负整数 。
输入格式
第一行包含一个整数 ()— 测试用例的数量。
每个测试用例的第一行包含一个整数 ()— 初始多重集中不同整数的数量。
接下来 行,每行包含两个整数 和 (,),表示整数 在初始多重集中恰好出现 次。
整数 两两不同。
保证所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一个整数 — 在任意时刻多重集中可能出现的最大整数。
样例
10
4
2 2
0 3
4 1
1 2
1
10 1
1
2 3
3
0 1
2 2
3 1
3
0 4
1 2
2 1
1
0 100
2
2 7
3 1
2
0 1
3 3
3
0 1
1 1
59 1
4
0 5
1 1
2 3
3 1
5
10
3
4
4
7
4
3
59
5
说明
在第一个测试用例中,初始多重集为 。
我们可以将 替换为 ,得到 。然后,我们可以将 替换为 。
可以证明不会出现大于 的整数,因此答案为 。
在第二个测试用例中, 已经出现在初始多重集中,且不会出现更大的整数。因此答案为 。
来源
导入自 Codeforces — Codeforces Round 1122 (Div. 3)。