2663.cpp

#include <iostream>
#include <vector>
#include <list>
#include <map>
//#include <unordered_map>
#include <algorithm>
#include <string>
#include <memory>  
#include <cstring>
using namespace std;

#include <stdio.h>
#include <stdlib.h>

const int MAXN = 30;
long long c[MAXN][8];

long long solve(int cur, int state) {
  if (cur >= MAXN) {
    if (state == 0) return 1;
    else return 0;
  }
  if (c[cur][state] != -1) return c[cur][state];
  long long count = 0;
  switch(state) {
    case 0: //0 0 0
      count += solve(cur + 1, 7);
      count += solve(cur + 1, 1);
      count += solve(cur + 1, 4);
      break;
    case 1:
      count += solve(cur + 1, 0);
      count += solve(cur + 1, 6);
      break;
    case 2:
      count += solve(cur + 1, 5);
      break;
    case 3:
      count += solve(cur + 1, 4);
      break;
    case 4:
      count += solve(cur + 1, 3);
      count += solve(cur + 1, 0);
      break;
    case 5:
      count += solve(cur + 1, 2);
      break;
    case 6:
      count += solve(cur + 1, 1);
      break;
    case 7:
      count += solve(cur + 1, 0);
      break;
  }
  c[cur][state] = count;
  return c[cur][state];
}

int main() {
  memset(c, -1, sizeof(c));
  solve(0, 0);
  while (true) {
    int n;
    cin >> n;
    if (n == -1) break;
    if (n == 0) cout << 1 << endl;
    else if (n % 2) cout << 0 << endl;
    else cout << solve(MAXN - n, 0) << endl;
  }
  return 0;
}