好不容易A了一道题怎么能不写题解呢~
题目
链接
题目描述
一天小明坐在沙滩上玩石子,但是过了一会儿小明就玩腻了,于是他给自己出了一道难题:如果有一个棋盘,在棋盘外放置一粒石子,可以将其理解为第(0)个格子,然后需要在第一个格子里放入若干个石子,之后每一个格子放入前两个格子的石子数之和的石子,并且要满足第(a)个格子放(x)粒石子,并求出第(b)个格子有多少个石子。
当然小明没有那么聪明,他给你的条件可能是错误的(就是第(a)个格子可能没有(x)粒石子),所以当条件是错误的时候你要告诉小明这个条件不成立。
输入格式
该题有多组数据,请读到文件末结束。
对于每一组数据仅一行,(3)个正整数(a,x,b),分别表示第(a)个格子放了(x)粒石子,以及你所需要计算的是第(b)个格子的石子数量。
输出格式
对于每一次询问,仅(1)个整数,为第(b)个格子的石子数量,若小明说的情况不存在,那么请输出-1。
数据范围
对于(50\%)的数据:如果答案存在,那么(pleq50) 。
对于(100\%)的数据:(1leq)数据组数(leq10^4),(1leq a,bleq20),数据保证如果答案存在,那么(1leq pleq10^6) 。(注: (p)是第一格放置的石子数)。
思考
这道题嘛……很明显,就是一个斐波那契数列,虽然我考试的时候不是这么写的
这里我们有一个更简洁,好用,简单的算法————
打表
是的没错,就是打表
我们看一下数据范围:(1leq a,bleq20)。那没事儿啊这么点数据范围心里瞬间有底了
那我们就可以打表啦~
我们先找一下规律:
设第一个格放了(x)个石子
就会变成这个亚子:
然后我们只要判断给出的数 减去 相对应的常数 取模 相对应的单项式
若 不等于 (0),就直接输出-1
AC Code
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long y[21] = {1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181};
long long z[21] = {0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765};
int main()
{
freopen("kela.in", "r", stdin);
freopen("kela.out", "w", stdout);
long long a, x, b;
while(~scanf("%lld%lld%lld", &a, &x, &b))
{
if((x - y[a]) % z[a] == 0)
printf("%lld
", z[b] * ((x - y[a]) / z[a]) + y[b]);
else
printf("-1
");
}
return 0;
}