fork download 
  1.  
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <map>
  7.  
  8. using namespace std;
  9.  
  10. const long long inf = 1000000000000000000LL;
  11.  
  12. vector<long long> fib;
  13. map<long long, int> f;
  14.  
  15. int solve(long long x) {
  16. 	if (f.count(x) > 0) return f[x];
  17. 	int t = lower_bound(fib.begin(), fib.end(), x) - fib.begin();
  18. 	if (fib[t] == x) {
  19. 		f[x] = 1;
  20. 		return 1;
  21. 	}
  22. 	int res = min(solve(fib[t] - x), solve(x - fib[t-1])) + 1;
  23. 	f[x] = res;
  24. 	return res;
  25. }
  26.  
  27. int main() {
  28. 	fib.push_back(1);
  29. 	fib.push_back(2);
  30. 	long long a = 1, b = 2;
  31. 	while (true) {
  32. 		long long c = a + b;
  33. 		if (c > inf) break;
  34. 		fib.push_back(c);
  35. 		a = b;
  36. 		b = c;
  37. 	}
  38.  
  39. 	int q;
  40. 	scanf("%d", &q);
  41. 	for (int i = 0; i < q; i ++) {
  42. 		long long x;
  43. 		scanf("%lld", &x);
  44. 		printf("%d\n", solve(x));
  45. 	}
  46.  
  47. 	return 0;
  48. }
  49.  
Success #stdin #stdout 0.01s 2864KB
comments (?)
stdin 
1
1070
stdout 
4
https://ideone.com/7D5DV
language:
C++ (gcc 8.3)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!