欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JZOJ 3461. 【NOIP2013模拟联考5】小麦亩产一千八(kela)

程序员文章站 2023-10-17 23:23:24
3461. 【NOIP2013模拟联考5】小麦亩产一千八(kela) (Standard IO) Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits Goto ProblemSet 3461. 【NOIP2013模拟联考5】小麦 ......

Description

“有了金坷垃,肥料一袋能顶两袋撒,小麦亩产一千八,吸收两米下的氮磷钾……”,话说HYSBZ(Hengyang School for Boys & Zy)学识渊博孩纸们一讲到粮食,都会想起印度那个著名的故事:国王要在第一个格子里放入一粒小麦,接下来的格子放入前面一个格子的两倍的小麦。这样所需小麦总数是巨大的,哪是不用金坷垃就能完成的任务?不过为了减轻国王的任务,那个下棋获胜的宰相换了一个要求:“我只需要你在棋盘外放一粒小麦,可以将其理解为第0 个格子,然后你需要在第一个格子里放入p粒小麦,之后每一个格子放入前两个格子的小麦数之和的小麦,并且要满足第a 个格子放x 粒小麦,第b 个格子放……”说到这,宰相突然发现自己说的满足第a 个格子放x 粒小麦的情况可能不存在……欺君可是大罪啊!国王看到宰相迟迟不说,自己也烦了!我自己来算!于是国王拜托你,让你算出第b 个格子应该放几粒小麦。当然,就算答案不存在,你也是要告诉国王的。
 

Input

该题有多组数据,请读到文件末结束。

对于每一组数据仅一行,3 个正整数a,x,b,分别表示第a 个格子放了x 粒小麦,以及你所需要计算的是第b 个格子的小麦数量。

Output

对于每一次询问,仅1 个整数,为第b 个格子的小麦数量,若宰相说的情况不存在,那么请输出-1。
 

Sample Input

1 1 2
3 5 4
3 4 6
12 17801 19

Sample Output

2
8
-1
516847
【样例解释】
对于样例二,f[1]=2 时,能够满足f[3]=5,因此宰相没有撒谎,此时第5 个格子的小麦数应为f[4]=f[2]+f[3]=3+5=8.
 
 
做法:这不就自行定义F[1]的菲波那切数列吗。。根据性质算就行啦
 
代码如下:
JZOJ 3461. 【NOIP2013模拟联考5】小麦亩产一千八(kela)
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <string>
 5 #include <algorithm>
 6 #include <cmath>
 7 #define LL long long
 8 using namespace std;
 9 LL a, b, x;
10 LL f[40];
11 
12 LL max(LL a, LL b){
13     return a > b ? a : b;
14 }
15 
16 void pre_work()
17 {
18     f[1] = 1;
19     for (int i = 2; i <= 25; i++)
20         f[i] = f[i - 1] + f[i - 2];
21 }
22 
23 int main()
24 {
25     pre_work();
26     while (~scanf("%lld%lld%lld", &a, &x, &b))
27     {
28         LL f1 = 0;
29         if ((x - f[max(a - 1, 0)]) % f[max(a, 1)] != 0)
30         {
31             printf("-1\n");
32             continue;
33         }
34         f1 = (x - f[max(a - 1, 0)]) / f[max(a, 1)];
35         printf("%lld\n", f[max(b, 0)] * f1 + f[max(b - 1, 0)]);
36     }
37 }
View Code