# Untitled

Apr 8th, 2020
1,537
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<iostream>
2. #include<vector>
3. #include<math.h>
4.
5. using namespace std;
6.
7. bool isPerfectSquare(int x)
8. {
9.     int s = sqrt(x);
10.     return (s * s == x);
11. }
12.
13. bool isFibonacci(int n)
14. {
15.
16.     return isPerfectSquare(5 * n * n + 4) ||
17.            isPerfectSquare(5 * n * n - 4);
18. }
19.
20. vector <int> relleno (vector <int> v, int i){
21.     v[i] = v[i - 1] + v[i - 2];
22.     i++;
23.     if(i < v.size()) return relleno(v, i);
24.     else return v;
25. }
26.
27. void casos(vector <bool> v, int i, vector <int> fibonacci){
28.     bool completo = false;
29.     int k = i;
30.       for(int j = 0; j < 25; j++){
31.           if(fibonacci[j] == k || v[i - k]){ v[i] = false; completo = true;}
32.           else k--;
33.       }
34.       if(!completo) v[i] = true;
35.     if (v.size() < pow(10, 5)) casos(v, i++, fibonacci);
36.     else return;
37. }
38.
39.
40. int main(){
41.     vector <bool> guanya1 (pow(10, 5));
42.     int n;
43.     vector <int> fibonacci (25);
44.     fibonacci[0] = 1;
45.     fibonacci[1] = 1;
46.     relleno(fibonacci, 2);
47.     guanya1[0] = false;
48.     guanya1[1] = true;
49.     casos(guanya1, 2, fibonacci);
50.     while(cin >> n){
51.       if (isFibonacci(n)) cout << 1 << endl;
52.       else if(guanya1[n]) cout << 1 << endl;
53.       else cout << 2 << endl;
54.     }
55. }
RAW Paste Data