#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> bus(int n, const vector<int>& A, const vector<int>& B, const vector<int> C)
{
  vector<int> res(n), diff(n);
  for (int i = 0; i < A.size(); i++)
  {
    diff[A[i] - 1] += C[i];
    diff[B[i] - 1] -= C[i];
  }
  res[0] = diff[0];
  for (int i = 1; i < n; i++)
  {
    res[i] = res[i - 1] + diff[i];
  }
  return res;
}

int subsequence(const string & s)
{
  vector<int> c(26);
  int l = 0, r = 1, res = 1;
  c[s[0] - 'a']++;

  while(r < s.size())
  {
    if (c[s[r] - 'a'])
    {
      while(s[l] != s[r])
      {
	c[s[l] - 'a']--;
	l++;
      }
    }
    res = max(res, r - l);
    c[s[r] - 'a']++;
    r++;
  }
  return res;
}

int chocolate(int n)
{
  vector<int> a(n + 1);
  a[1] = 1;
  a[2] = 2;
  a[3] = 4;
  for (int i = 4; i <= n; i++)
  {
    a[i] = a[i - 1] + a[i - 2] + a[i - 3];
  }
  return a[n];
}

int main()
{
  cout << chocolate(3) << endl;
  cout << chocolate(4) << endl;
  cout << chocolate(6) << endl;
  cout << chocolate(8) << endl;
  // cout << subsequence("abcabcbb") << endl;
  // cout << subsequence("ababcd") << endl;

  // vector<int> res = bus(4, {1, 2, 2}, {2, 3, 4}, {4, 8, 12});
  // for (int i: res) 
  //   cout << i << '\t';
  // return 0;
  
}