题目描述

火车从始发站（称为第 1 站）开出，在始发站上车的人数为 a，然后到达第 2 站，在第 2 站有人上、下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前）车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 (n-1) 站），都满足此规律。现给出的条件是：共有 n 个车站，始发站上车的人数为 a ，最后一站下车的人数是 m（全部下车）。试问 x 站开出时车上的人数是多少？

输入格式

输入只有一行四个整数，分别表示始发站上车人数 a，车站数 n，终点站下车人数 m 和所求的站点编号 x。

输出格式

输出一行一个整数表示答案：从 xx 站开出时车上的人数。

输入输出样例

输入 #1：

5 7 32 4

输出 #1：

说明/提示

对于全部的测试点，保证 1≤a≤20，1≤x≤n≤20，1≤m≤2×10^4。

思路：

在做之前，我们先找找规律：

第一站：上车 a 人；车上有 a 人；
第二站：假设上车 u 人，则下车 u 人；车上仍然是a人；
第三站：上车人数等于前两站上车人数之和：a+u 人，下车人数等于上次上车人数 u 人；净上车人数为 a 人；车上有 2a 人；
第四站：上车人数 =a+2u，下车人数 =a+u；净上车人数 =u；车上有多少人呢？就是 2a+u；
第五站：上车人数 =2a+3u，下车人数 =a+2u，净上车人数 =a+u；车上有 3a+2u 人；
第六站：上车人数 =3a+5u，下车 2a+3u人，净上车人数 =a+2u；车上有 4a+4u人……

这里不必在列下去了，发现规律了吗？

将第三站净上车人数看作x1，第四站看作x2，第五站为x3，第六站为x4，有 x1+x2=x3, \ x2+x3=x4…x1+x2=x3, x2+x3=x4…这不是斐波那契数列么？

知道了起始人数aa，知道了终止人数，这里的u就可求了；不过计算机不认识方程，所以我们要想个办法：

因此我们要把a和u分开处理！！！

我们不妨把每一站中a的关系看作a的斐波那契数列，而u的关系看作u的斐波那契数列

由于是从第三站开始出现了这样的规律，所以第一项为第三站，第二项就是第四站

我们不妨自己再次总结a的规律，于是得到下面的代码:

		int p=1,q=0,k=0,sum1=0;for(int i=1;i<=n-5;i++){k=p+q;sum1+=k;p=q;q=k;}

常规斐波那契就不解释了，但注意，这里统计的sum1是a的系数！

细心的小伙伴就会发现了，这里满足的条件是n>5,其实n≤5也可以，但是代码较为复杂，后面说；

且注意：第三项a的系数为1，第四项为0，所以定义p=1，q=0；这里 sum1=sum1+2（从第五项开始计算，前面还有2a，不能忽略）

同样的，我们得到了计算u系数的代码

		int e=0,t=1,g=0,sum2=0;for(int i=1;i<=n-5;i++){g=e+t;sum2+=g;e=t;t=g;}

同样的sum2=sum2+1；（第五项开始算，前面还有一个u）那么u=?这个大家自己思考，后面给代码再给答案；

以上内容针对n>5，那么我们就可以较为整齐地处理n≤5的情况了。

这个如何处理？

大家思考一下，根据我们列出的上面的式子，车站数是肯定≥2的，车最少要经过两站。那么无论n=2还是3，输出的不都是a么？后面的大家自己推理；

那么对于n≤3也讨论完了，对于n>3呢？

这时又与x有关了，根据上面推导的斐波那契数列的规律，那到第x站的a有几个？u有几个？（人数 =t*a+i*u）还是需要分类讨论的，没有做的思考一下，再看下面代码:

if(x<=5){if(x==1||x==2)cout<<？;else if(x==3)cout<<？;else if(x==4)cout<<？;else if(x==5)cout<<？;}else{for(int i=1;i<=x-？;i++){k=p+q;sum1+=k;p=q;q=k;}sum1+=2;for(int i=1;i<=x-？;i++){g=e+t;sum2+=g;e=t;t=g;}sum2+=1;

这里的“？”是什么供大家思考，参考我们以上的推导.

完整代码：

    #includeusing namespace std;int a, n, m, x, u=1, z, y;int main(){scanf("%d %d %d %d", &a, &n, &m, &x); if(n <= 5) {if(n == 2||n == 3)printf("%d", a);else if(n == 4) {if(x == 1 || x == 2) printf("%d", a);else if(x == 3) printf("%d", a * 2);}else if(n == 5) {if(x == 1 || x == 2) printf("%d", a);else if(x == 3) printf("%d", a * 2);else if(x == 4) printf("%d", (m - a * 3) / 2 + a * 2);}}else {int p = 1, q = 0, k = 0, sum1 = 0;for(int i = 1; i <= n - 5; i++) { 	k = p + q;sum1 += k;p = q;q = k;}int s1 = sum1 + 2;int e = 0, t = 1, g = 0,sum2 = 0;for(int i = 1; i <= n - 5; i++) {g = e + t;sum2 += g;e = t;t = g;}int s2 = sum2 + 1;int S = (m - s1 * a) / s2;q = k = e = g = sum1 = sum2 = 0;p = t = 1;if(x <= 5) {if(x == 1 || x == 2) printf("%d", a);else if(x == 3)  printf("%d", a * 2);else if(x == 4) printf("%d", S + a * 2);else printf("%d", S * 2 + a * 3);}else {for(int i = 1; i <= x - 4; i++) {k = p + q;sum1 += k;p = q;q = k;}sum1 += 2;for(int i = 1; i <= x - 4; i++) {g = e + t;sum2 += g;e = t;t = g;}sum2 += 1;printf("%d", sum1 * a + sum2 * S);}}return 0;}