[NOIP1998 提高组] 车站

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

5 7 32 4

样例输出 #1

13

提示

对于全部的测试点，保证 $1\le a\le 20$，$1\le x\le n\le 20$，1≤m≤2×1041 \\leq m \\leq 2 \\times 10^41≤m≤2×104。

所需变量

int a;//代表第一站上车人数

int n;//代表站数

int m;//代表重点下车人数

int x;//代表我们所求的站点

int arr[25] = {0};//代表第i站上车人的a的系数

int tri[25] = {0};//代表第i站上车人数的x的系数

int sum[25][2] = {0};//代表目前该站的总人数

思路：如图所示上面的序号代表的第几站，然后序号下面第一个数代表该站有多少人，第二个代表会上车多少人，第三行代表会下车多少人！
通过往后多推几项就不难发现，第五站总人数在第四站的基础上加了第三站上车的人！
因此当我们发现规律后，我们就能推出每一站的人数了！

arr[2] = 0;
arr[3] = 1;
tri[2] = 1;
tri[3] = 1;
sum[2][0] = 1;
sum[3][0] = 2;
sum[2][1] = 0;
sum[3][1] = 0;
for(i = 4;i<n;i++){arr[i] = arr[i-1] + arr[i-2];tri[i] = tri[i-1] + tri[i-2];sum[i][0] = sum[i-1][0] + arr[i-2];sum[i][1] = sum[i-1][1] + tri[i-2];
}

由于我们知道第n站的总人数，又由于我们知道a，一个一元一次方程，求出x我们就能得到我们想求的第x站的人数
所求的方法如下：

temp = (m - sum[n-1][0]*a)/sum[n-1][1];num = sum[x][0]*a + sum[x][1]*temp;

得到我们想求的站的人数后，将其输出出来就可以
代码如下（编译器是dev，语言是C语言）：

#include<iostream>
using namespace std;
int main(){int a,n,m,x,arr[25] = {0},tri[25] = {0},sum[25][2] = {0};int i,temp = 0,num;cin>>a>>n>>m>>x;if(x == 1||x == 2){cout<<a<<endl;}else if(x == 3){cout<<2*a<<endl;}else{arr[2] = 0;arr[3] = 1;tri[2] = 1;tri[3] = 1;sum[2][0] = 1;sum[3][0] = 2;sum[2][1] = 0;sum[3][1] = 0;for(i = 4;i<n;i++){arr[i] = arr[i-1] + arr[i-2];tri[i] = tri[i-1] + tri[i-2];sum[i][0] = sum[i-1][0] + arr[i-2];sum[i][1] = sum[i-1][1] + tri[i-2];}temp = (m - sum[n-1][0]*a)/sum[n-1][1];num = sum[x][0]*a + sum[x][1]*temp;cout<<num<<endl;}return 0;
}