#include <iostream>
using namespace std;
  
int countWays(int n) {
    int A[n + 1], B[n + 1];
    A[0] = 1, A[1] = 0, B[0] = 0, B[1] = 1;
    for (int i = 2; i <= n; i++) {
        A[i] = A[i - 2] + 2 * B[i - 1];
        B[i] = A[i - 1] + B[i - 2];
    }
  
    return A[n];
}
  
int main() {
    int n = 8;
    cout << countWays(n);
    return 0;
}

#include <iostream>
using namespace std;
 
int t[9][9];

int un_kp(int price[], int length[], int Max_len, int n) {
    if (n == 0 || Max_len == 0) return 0;
 
    if (length[n - 1] <= Max_len) t[n][Max_len] = max(price[n - 1] + un_kp(price, length, Max_len - length[n - 1], n), un_kp(price, length, Max_len, n - 1));
    else t[n][Max_len] = un_kp(price, length, Max_len, n - 1);
    
    return t[n][Max_len];
}

int main() {
    int price[] = { 1, 5, 8, 9, 10, 17, 17, 20 };
    int n = sizeof(price) / sizeof(price[0]);
    int length[n];
    for (int i = 0; i < n; i++) {
        length[i] = i + 1;
    }
    int Max_len = n;

    cout << "Maximum obtained value  is " << un_kp(price, length, n, Max_len) << endl;
}

#include <bits/stdc++.h>
using namespace std;

struct area {
    int a, b;
    area(int a, int b) : a(a), b(b)
    {}
};

int max(int a, int b, int c) {
    return max(a, max(b, c));
}

int maxSurvival(int A, int B, area X, area Y, area Z,
                int last, map<pair<int, int>, int>& memo) {
    if (A <= 0 || B <= 0) return 0;
    pair<int, int> cur = make_pair(A, B);=
    if (memo.find(cur) != memo.end()) return memo[cur];
    int temp;

    switch(last) {
    case 1:
        temp = 1 + max(maxSurvival(A + Y.a, B + Y.b,
                                   X, Y, Z, 2, memo),
                       maxSurvival(A + Z.a, B + Z.b,
                                  X, Y, Z, 3, memo));
        break;
    case 2:
        temp = 1 + max(maxSurvival(A + X.a, B + X.b,
                                  X, Y, Z, 1, memo),
                       maxSurvival(A + Z.a, B + Z.b,
                                  X, Y, Z, 3, memo));
        break;
    case 3:
        temp = 1 + max(maxSurvival(A + X.a, B + X.b,
                                  X, Y, Z, 1, memo),
                       maxSurvival(A + Y.a, B + Y.b,
                                  X, Y, Z, 2, memo));
        break;
    }
  
    memo[cur] = temp; 
    return temp;
}
  
int getMaxSurvivalTime(int A, int B, area X, area Y, area Z) {
    if (A <= 0 || B <= 0) return 0;
    map< pair<int, int>, int > memo;
    return
        max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo),
            maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo),
            maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo));
}

int main() {
    area X(3, 2);
    area Y(-5, -10);
    area Z(-20, 5);
  
    int A = 20;
    int B = 8;
    cout << getMaxSurvivalTime(A, B, X, Y, Z);
  
    return 0;
}

using namespace std;

long long moduloMultiplication(long long a, long long b, long long mod) {
    long long res = 0;
    a %= mod;
 
    while (b) {
        if (b & 1)  res = (res + a) % mod;
        a = (2 * a) % mod;
        b >>= 1; // b = b / 2
    }
    return res;
}

long long int modInverse(long long int b, long long int m) {
    long long int x, y;
    long long int g = gcdExtended(b, m, &x, &y);

    if (g != 1) return -1;
    return (x % m + m) % m;
}
 
// Euclidean Algorithm (used to find modular inverse)
long long int gcdExtended(long long int a, long long int b,  long long int* x, long long int* y) {
    if (a == 0) {
        *x = 0, *y = 1;
        return b;
    }
 
    long long int x1, y1;
    long long int gcd = gcdExtended(b % a, a, &x1, &y1);
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}
 
long long int modDivide(long long int a, long long int b, long long int m) {
    a = a % m;
    long long int inv = modInverse(b, m);
    if (inv == -1) return 0;
    else return (inv * a) % m;
}
 
int nCr(int n, int r, int p) {
    if (r > n) return 0;
    if (r > n - r) r = n - r;
    long long int x = 1;

    for (int i = 1; i <= r; i++) {
        x = moduloMultiplication(x, (n + 1 - i), p);
        x = modDivide(x, i, p);
    }
    return x;
}
 
int main() {
    long long int n = 5, r = 3, p = 1000000007;
    cout << "Value of nCr % p is " << nCr(n, r, p);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int largestSubset(int a[], int n) {
    int dp[n];
    dp[n - 1] = 1;
 
    for (int i = n - 2; i >= 0; i--) {
        int mxm = 0;
        for (int j = i + 1; j < n; j++)
            if (a[j] % a[i] == 0 || a[i] % a[j] == 0)
                mxm = max(mxm, dp[j]);
 
        dp[i] = 1 + mxm;
    }

    return *max_element(dp, dp + n);
}

int main() {
    int a[] = { 1, 3, 6, 13, 17, 18 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << largestSubset(a, n) << endl;
    return 0;
}