NOI / 2.1基本算法之枚举-8759:火车上的人数

8759:火车上的人数

总时间限制:

1000ms

内存限制:

65536kB

描述

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

输入

一行，包含四个整数a，n，m和x，相邻两个整数之间用单个空格隔开。0 <= a <= 10, 3 <= x < n <= 15, 0 <= m <= 10000。

题目保证数据有唯一解。允许有人在同一站上下车。

输出

一个整数，为从x站开出时车上的人数。

样例输入

5 7 32 4

样例输出

来源

NOIP1998复赛提高组第一题

参考答案：

#include<bits/stdc++.h>

using namespace std;

int main()

{

	int a,b[20],c[20],d[20],m,n,i,j,x;

	cin>>a>>n>>m>>x;

	b[1]=a;

	c[1]=0;

	d[1]=a;

	for(i=1;;i++)

	{

		b[2]=i;

		c[2]=i;

		d[2]=a;

		for(j=3;j<=n-1;j++)

		{

		    b[j]=b[j-1]+b[j-2];

		    c[j]=b[j-1];

		    d[j]=d[j-1]+b[j]-c[j];

		    if(d[n-1]==m)

		    {

		    	cout<<d[x];

		    	return 0;

		    }

		}

	}

	return 0;

}

巴特西

NOI / 2.1基本算法之枚举-8759:火车上的人数

8759:火车上的人数

最新文章

热门文章

巴特西

NOI / 2.1基本算法之枚举-8759:火车上的人数

8759:火车上的人数​​​​​​

最新文章

热门文章

8759:火车上的人数