题意
给定根木棍,木棍的长度范围是,问:根据这些木棍,是否一定能选出三根构造出一个三角形?
题解
思考一下,根木棍在什么情况下无法构造出三角形?
若根木棍从小到大的长度依次为:,即 .任选三根木棍的长度为。当此三根木棍无法构造出三角形时,必定存在.因而当根木棍无法构造出一个三角形时,必定存在如下关系:.
在最坏情况下,当给定木棍无法构造出一个三角形时,它们的数学关系满足如下条件:
当时,我们根据这些木棍无法构造出一个三角形,否则我们一定能够构造出一个三角形.
显然,具备指数级别的增长速度。和斐波那契数列相似,时, 已超过数据范围.
判定最坏情况下无法构造出三角形的时间复杂度为:,显然符合时间限制.
注:的增长速度为指数级别,当时应直接,否则可能会爆.
Code
C \ C++
#include<stdio.h>
typedef long long i64;
int calc(i64 l,i64 r){
int res = 3;
i64 a = l,b = l,c = l + l;
while(c<=r){
i64 t = b + c;
a = b,b = c,c = t;
res++;
}
return res;
}
int main(){
int T; scanf("%d",&T);
while(T--){
i64 k,l,r;
scanf("%lld %lld %lld",&k,&l,&r);
printf("%s\n",k>=calc(l,r)?"YES":"NO");
}
}
Python
import sys
input = lambda: sys.stdin.readline().strip()
def main():
import sys
data = sys.stdin.read().split()
T = int(data[0])
ptr = 1
res = []
for _ in range(T):
k = int(data[ptr])
l = int(data[ptr + 1])
r = int(data[ptr + 2])
ptr += 3
# 构建最大三角形无法成立的集合
f = 2 # 初始有两个元素 l, l
s1 = l
s2 = l
while True:
s3 = s1 + s2
if s3 > r:
break
f += 1
s1 = s2
s2 = s3
if k > f:
res.append("YES")
else:
res.append("NO")
print('\n'.join(res))
if __name__ == "__main__":
main()