2 shunfurh shunfurh 于 2017.01.11 13:30 提问

Revenge of Fibonacci

Problem Description
The well-known Fibonacci sequence is defined as following:

Here we regard n as the index of the Fibonacci number F(n).
This sequence has been studied since the publication of Fibonacci's book Liber Abaci. So far, many properties of this sequence have been introduced.
You had been interested in this sequence, while after reading lots of papers about it. You think there’s no need to research in it anymore because of the lack of its unrevealed properties. Yesterday, you decided to study some other sequences like Lucas sequence instead.
Fibonacci came into your dream last night. “Stupid human beings. Lots of important properties of Fibonacci sequence have not been studied by anyone, for example, from the Fibonacci number 347746739…”
You woke up and couldn’t remember the whole number except the first few digits Fibonacci told you. You decided to write a program to find this number out in order to continue your research on Fibonacci sequence.

Input
There are multiple test cases. The first line of input contains a single integer T denoting the number of test cases (T<=50000).
For each test case, there is a single line containing one non-empty string made up of at most 40 digits. And there won’t be any unnecessary leading zeroes.

Output
For each test case, output the smallest index of the smallest Fibonacci number whose decimal notation begins with the given digits. If no Fibonacci number with index smaller than 100000 satisfy that condition, output -1 instead – you think what Fibonacci wants to told you beyonds your ability.

Sample Input
15
1
12
123
1234
12345
9
98
987
9876
98765
89
32
51075176167176176176
347746739
5610

Sample Output
Case #1: 0
Case #2: 25
Case #3: 226
Case #4: 1628
Case #5: 49516
Case #6: 15
Case #7: 15
Case #8: 15
Case #9: 43764
Case #10: 49750
Case #11: 10
Case #12: 51
Case #13: -1
Case #14: 1233
Case #15: 22374

1个回答

dabocaiqq
dabocaiqq   2017.01.14 22:49
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
算法竞赛入门经典 第二版 习题5-15 Fibonacci的复仇 Revenge of Fibonacci uva12333
题目:https://vjudge.net/problem/UVA-12333思路: 大整数类+字典树 一开始套刘汝佳大整数类的板子套出好多问题,之后自己用string重新封装了一个。 用大整数类求出斐波那契数列然后将前42位插入字典树,便于之后查找前缀。这题做出了灵异事件,在自己机器上预处理好几分钟都跑不完结果交上去竟然AC了。。。。。代码:c++#include <cstdio> #incl
UVa12333 - Revenge of Fibonacci
#include #include #include #include using namespace std; #define nodesize 4000004 #define dictsize 10 typedef struct node1 { int id; int flag; node1* next[dictsize]; }tnode; tnode dict[nod
UVA 12333 Revenge of Fibonacci
题意:给你一个40 位的数 判断时在斐波那契数列的第一个数的前缀 没仔细看数据范围 原以为只是大数版题就放在C结果做的时候才发现数据量很大 还要加个字典树 套这两个版子就没什么问题了 预先用大数跑出斐波那契数列的结果 存在字典树里 询问的时候查询即可 #include #include #include #include #include #include #include #include
UVa 12333 - Revenge of Fibonacci (大数 + 字典树)
挺简单的一道字典树,注意计算范围, 如果序号大于等于100000就返回-1。 套用的刘汝佳的大数加法。
UVa 12333 - Revenge of Fibonacci
题目:给你一个数字串,判断他是哪一个Fib数的前缀,有多种答案输出最小的,不存在输出-1。 分析:字符串,大整数。             首先,利用大整数计算Fib的前100000项,由于数据较大,只储存前50位即可。             然后,按Fib的顺序存入字典树,利用滚动数组一边生成一边存储,可以减少内存开销。                         在存的过程中直接
[刷题]算法竞赛入门经典(第2版) 5-15/UVa12333 - Revenge of Fibonacci
题意:在前100000个Fibonacci(以下简称F)数字里,能否在这100000个F里找出以某些数字作为开头的F。要求找出下标最小的。没找到输出-1。代码:(Accepted,0.250s)//UVa12333 - Revenge of Fibonacci //Accepted 0.250s //#define _XIENAOBAN_ #include<iostream> #include<cs
紫书第五章习题 5-15 UVa 12333 - Revenge of Fibonacci
出处:https://blog.csdn.net/mobius_strip/article/details/27053639题目链接:https://vjudge.net/contest/231030#problem/O题目:给你一个数字串,判断他是哪一个Fib数的前缀,有多种答案输出最小的,不存在输出-1。分析:字符串,大整数。            首先,利用大整数计算Fib的前100000项...
UVA12333--Revenge of Fibonacci
题意: 给你一个数字串,判断他是哪一个Fib数的前缀,有多种答案输出最小的,不存在输出-1。思路: 大数加法计算斐波那契数,字典树搜索 计算过程中进行字典树的创建,计算时,当斐波那契数大于50位时,只计算高50位即可。代码:#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #define ma
UVa 12333 – Revenge of Fibonacci [大数+字典树]
题目:给你一个数字串,判断他是哪一个Fib数的前缀,有多种答案输出最小的,不存在输出-1。 解题思路:首先题目要求在100000个Fibonacci数之内,说明数字非常大,我们要用大数的方法存储,也就是用char[]来存储每个位上的数字 还有一个关键点是查找,我们使用字典树来解决,这样才可能不超时。字典树的意思就是使用每个节点来存储0-9,节点下面又有子节点,同样存储0-9一直下去例如 -1
HDURevenge of Fibonacci --- 高精度 + 斐波那契数列 + 字典树
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 204800/204800 K (Java/Others) Total Submission(s): 2110    Accepted Submission(s): 504 Problem Description The well-known Fibonacci