洛谷 P1011 车站

洛谷 P1011 车站

链接

https://www.luogu.org/problem/P1011

题目

题目描述

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

输入格式

a(≤20),n(≤20),m(≤2000),和x(≤20),

输出格式

从x站开出时车上的人数。

输入输出样例

输入 #1

  5 7 32 4

输出 #1

  13

图解

站序号(i) 上车(f) 下车(g) 剩余人数(k)
1 a 0 a
2 t t a
3 a+t t 2a
4 a+2t a+t 2a+t
5 2a+3t a+2t 3a+2t
6 0 3a+2t 0

思路

总结一下规律(中间几站)

1. 每一站下车人数等于上一站上车人数
2. 每一站上车人数等于前两站上车人数和

我们假设第6站就全部下车,可以得到图解中的表格,归纳总结可以发现
(s为斐波那契数列,直接可以计算)

1. g(i) = f(i-1)
2. f(i) = f(i-1) + f(i-2)
3. g(n) = f(n-1) + a - t = m
4. f(i) = s(i-2)*a + s(i-1)*t
5. k(i) = f(i) + f(1) - g(2)

之后我们就能发现,我们需要的k(x) = f(x) + a - t,推导后只需要两个等式

1. m - [s(n-3) + 1]*a = [s(n-2) - 1]*t
2. k(x) = [s(x-2) + 1]*a + [s(x-1) - 1]*t

给了我们m,a,n,我们由公式1算出t,公式2算出k(x)即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>

using namespace std;


int main()
{

int a,n,m,x,t;
cin>>a>>n>>m>>x;
int s[n];
s[1]=1;
s[2]=1;
for(int i=3;i<=n;i++)
s[i]=s[i-1]+s[i-2];

t=(m-(s[n-3]+1)*a)/(s[n-2]-1);
cout<<(s[x-2]+1)*a+(s[x-1]-1)*t;

return 0;
}
---本文结束,感谢阅读---