180. 地铁站

单点时限: 2.0 sec

内存限制: 256 MB

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

输入格式

输入为 个整数 ，表意见题面

输出格式

输出为 个整数，表示从 站开出时车上的人数

样例

input

5 7 32 4

output

13

提示

保证所有数据均为整数

/*
思路：当前x站增加为人数为n-2站上车人数。
关键找第二站上车人数，注意此时的上车人数可能大于a。
*/
#include<iostream>
using namespace std;
int main() {
	int n,a,m,x;
	cin>>a>>n>>m>>x;
	int dp[n+1];
	dp[1]=dp[2]=a;
	dp[n]=0;
	int shangche[n+1];
	dp[3]=2*a;
	cha[1]=a;
	if(x<=3)
		cout<<dp[x]<<endl;
	else
		for(int i = 20; i>=0 ; i--) {
			shangche[2]=i;
			for(int j = 3; j < n; j++) {
				dp[j]=dp[j-1]+cha[j-2];
				shangche[j]=shangche[j-1]+shangche[j-2];
			}
			if(dp[n-1]==m) {
				cout<<dp[x]<<endl;
				break;
			}
		}
	return 0;
}