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;
}