深圳网站建设 设计贝尔利,wordpress 改成 中文字体,phpcms v9 网站名称标签,国内做的比较好的协会网站问题描述
小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有两位同学的卡片都是一样的。
给定 n, 请问小蓝的卡片至少有多少种?
输入格式
输入一行包含一个正整数表示 n 。
输出…问题描述
小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有两位同学的卡片都是一样的。
给定 n, 请问小蓝的卡片至少有多少种?
输入格式
输入一行包含一个正整数表示 n 。
输出格式
输出一行包含一个整数, 表示答案。
样例输入
6样例输出
3样例说明
小朋友们手中的卡片可能是: (1,1),(1,2),(1,3),(2,2),(2,3),(3,3)(1,1),(1,2),(1,3),(2,2),(2,3),(3,3) 。
评测用例规模与约定
对于 50% 的评测用例, 1≤n≤10^4 。
对于所有评测用例, 1≤n≤10^9 。
运行限制
最大运行时间1s最大运行内存: 256M问题分析
这是一个组合数问题需要注意的有两点
两张同样的卡片也可以作为一种组合所以跳出循环的条件是 c(k,2)kn 。根据组合数的公式很容易用代码实现。计算组合数的复杂度主要集中在求解阶乘的过程中。考虑到 n 的最大值为10^9需要使用记忆化数组来缩短计算时间。在这类比赛中程序处理千万级的运算量时已经很勉强了所以我在这里将记忆化数组的长度设为10^7即一千万。Python代码如下
nint(input())
dp[-1 for i in range(10**7)] # 阶乘数的记忆化数组# 阶乘
def fact(X):ans1 # 阶乘结果xXwhile x1:if dp[x]!-1: # 已知x的阶乘ans*dp[x]dp[X]ansreturn anselse:ans*xx-1dp[X]ansreturn ans# 组合数
def c(n,m):return fact(n)/(fact(m)*fact(n-m))k0
while c(k,2)kn:k1print(k)
可惜的是由于无法将记忆化数组的长度设为10^9通过率只有80%。读者如发现不足之处欢迎批评指正。
