Advertisement
faunuss

Untitled

Aug 24th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int rec(int n, vector<int>& a){
  7.     if(a[n] !=0 ){
  8.         return a[n];
  9.     }
  10.     if(n % 3 == 0){
  11.         int k = rec(n-1, a);
  12.         if(k == 2){
  13.             a[n] = 1;
  14.             return 1;
  15.         }
  16.         k = rec(n-2, a);
  17.         if(k == 2){
  18.             a[n] = 1;
  19.             return 1;
  20.         }
  21.         a[n] = 2;
  22.         return 2;
  23.     }
  24.     if(n % 3 == 1){
  25.         int k = rec(n-1, a);
  26.         if(k == 2){
  27.             a[n] = 1;
  28.             return 1;
  29.         }
  30.         k = rec(n-3, a);
  31.         if(k == 2){
  32.             a[n] = 1;
  33.             return 1;
  34.         }
  35.         a[n] = 2;
  36.         return 2;
  37.     }
  38.     if(n % 3 == 2){
  39.         int k = rec(n-1, a);
  40.         if(k == 2){
  41.             a[n] = 1;
  42.             return 1;
  43.         }
  44.         k = rec(n-2, a);
  45.         if(k == 2){
  46.             a[n] = 1;
  47.             return 1;
  48.         }
  49.         k = rec(n-3, a);
  50.         if(k == 2){
  51.             a[n] = 1;
  52.             return 1;
  53.         }
  54.         a[n] = 2;
  55.         return 2;
  56.     }
  57. }
  58.  
  59. int main() {
  60.     int N = 0;
  61.     cin >> N;
  62.     vector<int> a;
  63.     a.resize(N+1);
  64.  
  65.     a[0] = 2;
  66.     a[1] = 1;
  67.  
  68.     rec(N, a);
  69.     for(int i = 1; i < N+1; i++){
  70.         cout<< i <<  " - " << a[i] << "\n";
  71.  
  72.     }
  73.  
  74.  
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement