#P2155. R 集合

    ID: 1178 传统题 1000ms 256MiB 尝试: 62 已通过: 26 难度: 8 上传者: 标签>CF2400提高+/省选-Catalan 数双射计数反射原理补集计数组合数乘法递推高精度加法高精度减法高精度乘法高精度除法

R 集合

题目描述

设 sum⁡(S)\operatorname{sum}(S) 表示集合 SS 中所有元素的和。如果对于 SS 的任意两个不相交子集 AA 和 BB,如果他们满足:

  1. sum⁡(A)≠sum⁡(B)\operatorname{sum}(A) \neq \operatorname{sum}(B)
  2. $|A|\leq |B|\lor\operatorname{sum}(A) > \operatorname{sum}(B)$

则称 SS 是 R 集合。现在我们假设有一个大小为 nn,元素互不相等的集合,已经满足了条件 2,并且知道所有元素之间的大小关系。问最坏情况下最少需要几次比较才能确定它是不是 R 集合(修者按:比较是指选取两个集合判断它们的和是否相等)。

输入格式

输入的第一行包含一个整数 nn。

输出格式

输出一个整数,表示最少比较次数。

样例输入

4

样例输出

1

样例说明

设这个 4 元集的元素是 a1<a2<a3<a4a_1<a_2<a_3<a_4,那么我们只需要比较 sum⁡{a1,a4}\operatorname{sum}\{a_1,a_4\} 和 sum⁡{a2,a3}\operatorname{sum}\{a_2,a_3\}

数据规模与约定

一共有 20 个数据,对于第 i(1≤i≤20)i(1\leq i\leq 20) 个数据,n=i×50n=i\times 50。