Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int rec(int n, vector<int>& a){
- if(a[n] !=0 ){
- return a[n];
- }
- if(n % 3 == 0){
- int k = rec(n-1, a);
- if(k == 2){
- a[n] = 1;
- return 1;
- }
- k = rec(n-2, a);
- if(k == 2){
- a[n] = 1;
- return 1;
- }
- a[n] = 2;
- return 2;
- }
- if(n % 3 == 1){
- int k = rec(n-1, a);
- if(k == 2){
- a[n] = 1;
- return 1;
- }
- k = rec(n-3, a);
- if(k == 2){
- a[n] = 1;
- return 1;
- }
- a[n] = 2;
- return 2;
- }
- if(n % 3 == 2){
- int k = rec(n-1, a);
- if(k == 2){
- a[n] = 1;
- return 1;
- }
- k = rec(n-2, a);
- if(k == 2){
- a[n] = 1;
- return 1;
- }
- k = rec(n-3, a);
- if(k == 2){
- a[n] = 1;
- return 1;
- }
- a[n] = 2;
- return 2;
- }
- }
- int main() {
- int N = 0;
- cin >> N;
- vector<int> a;
- a.resize(N+1);
- a[0] = 2;
- a[1] = 1;
- rec(N, a);
- for(int i = 1; i < N+1; i++){
- cout<< i << " - " << a[i] << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement