fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <iomanip>
  7. #include <iostream>
  8. #include <map>
  9. #include <numeric>
  10. #include <queue>
  11. #include <set>
  12. #include <sstream>
  13. #include <stack>
  14. #include <string>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define ll long long
  21. // MAX (long long) 1000000000000000000
  22. // #define M 100 + 5
  23. #define N 200
  24.  
  25. #define MOD (ll)1000000007
  26. #define ld long double
  27. #define sz size()
  28. #define FOR(i, a, b) for (int i = a; i <= b; i++)
  29. #define FORD(i, a, b) for (int i = a; i >= b; i--)
  30. #define faster()                  \
  31.     ios_base::sync_with_stdio(0); \
  32.     cin.tie(NULL);                \
  33.     cout.tie(NULL);
  34. #define zero(n) setw(n) << setfill('0')
  35. #define stp(n) fixed << setprecision(n)
  36.  
  37. int main() {
  38.     int t;
  39.     cin >> t;
  40.  
  41.     ll f[50];
  42.     f[0] = 1;
  43.     f[1] = 0;
  44.  
  45.     for (int i = 2; i <= 45; i++) {
  46.         f[i] = f[i - 1] + f[i - 2];
  47.     }
  48.  
  49.     ll l[50];
  50.     l[0] = 1;
  51.     l[1] = 1;
  52.     for (int i = 2; i <= 45; i++) {
  53.         l[i] = l[i - 1] + l[i - 2];
  54.     }
  55.  
  56.     while (t--) {
  57.         int n, k;
  58.         cin >> n >> k;
  59.  
  60.         ll res = 0;
  61.  
  62.         while (k > 0 && n >= 0) {
  63.             if (k == l[n]) {
  64.                 res += f[n];
  65.                 break;
  66.             }
  67.             if (k >= l[n - 1]) {
  68.                 res += f[n - 1];
  69.                 k -= l[n - 1];
  70.                 n = n - 2;
  71.             }
  72.             else {
  73.                 n = n - 1;
  74.             }
  75.         }
  76.  
  77.         cout << res << endl;
  78.     }
  79.  
  80.     return 0;
  81. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
1
3 5
stdout
copy 
2
https://ideone.com/Px1KaH
language:
C++14 (gcc 8.3)
created:
30 days 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!