第十二届蓝桥杯省赛 - B组 杨辉三角形

第十二届蓝桥杯省赛 - B组 砝码称重
第十二届蓝桥杯省赛 - B组 时间显示
第十二届蓝桥杯省赛 - B组 双向排序

下面的图形是著名的杨辉三角形
如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
给定一个正整数 N,请你输出数列中第一次出现 N 是在第几个数?
输入格式
输入一个整数 N。
输出格式
输出一个整数代表答案。
数据范围
对于 20% 的评测用例,1≤N≤10;
对于所有评测用例,1≤N≤109
输入样例
6
输出样例
13

题解

这道题如果想要得满分,需要一点小技巧,详细步骤:
(1)我们先把杨辉三角形平均分成两半,因为在右半边的内容一定也会出现在左半边,所以我们只用看左半边,然后找规律即可。
第十二届蓝桥杯省赛 - B组 杨辉三角形_第1张图片
(2)通过上图可以发现每个斜行从右上到左下都是递增的,并且每行从左到右也是递增的。故每个斜行的第一个元素一定是该元素出现的第一个位置,只要从最下面的那个斜行开始枚举,就能找到目标元素。
第十二届蓝桥杯省赛 - B组 杨辉三角形_第2张图片
(3)那么我们接下来要找到前多少个斜行能够包含到最大值 109,通过计算 C1734 要大于 109,并且 C1632 要小于 109 。所以我们只用从第 16 斜行开始往下枚举即可。

代码

#include
using namespace std;
typedef long long LL;
LL n;

//求组合数
LL C(LL a, int b)
{
	LL res = 1;
	for (int i = a, j = 1; j <= b; i--, j++)
	{
		res = res * i / j;
		if (res > n)	return res;
	}
	return res;
}

bool check(int k)
{
	//下限是2*k,上限最差是n,当k=1时,C(n,1)=n
	LL l = 2 * k, r = max(n, l);
	while (l < r)
	{
		LL mid = l + r >> 1;
		if (C(mid, k) >= n)	r = mid;
		else l = mid + 1;
	}
	if (C(r, k) != n)	return false;
	//下标为r的位置前面有r+1行(等差公式得r*(r+1)/2)
	cout << (LL)r * (r + 1) / 2 + k + 1 << endl;
	return true;
}

int main()
{
	cin >> n;
	//从最大的斜行往前枚举
	for (int k = 16;; k--)
		if (check(k))
			break;
	return 0;
}

你可能感兴趣的