#P2675. 《瞿葩的数字游戏》T3-三角圣地
《瞿葩的数字游戏》T3-三角圣地
题目背景
国王1带大家到了数字王国的中心:三角圣地。
题目描述
不是说三角形是最稳定的图形嘛,数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字,分别是1~N。1~N可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来,最底端就是一个比较大的数字啦!数字王国称这个数字为“基”。国王1希望“基”越大越好,可是每次都自己去做加法太繁琐了,他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大,所以请你输出它mod 10007 的结果。
任务:给定N,求三角形1~N的基的最大值 再去 mod 10007。
输入格式
一个整数N
输出格式
一个整数,表示1~N构成的三角形的最大的“基”
4
24
1125
700
提示
数据:
20% 0<=N<=100
50% 0<=N<=3000
100% 0<=N<=1000000
样例解释:
1 3 4 2
4 7 6
11 13
24 是N=4的时候的最大值,当然还有别的构成形式。
PS:它叫做三角圣地,其实它就是个三角形~
本题数据已经更新,目前全部正确无误!
不要面向数据编程!