solution.cpp

#include <iostream>
#define LEFT 0
#define RIGHT 1
using namespace std;
int stage[40][2];
int main()
{
    int i;
    stage[1][LEFT] = 1;
    stage[1][RIGHT] = 0;
    stage[2][LEFT] = 1;
    stage[2][RIGHT] = 1;
    for (i = 3; i <= 39; i++)
    {
        stage[i][LEFT] = stage[i - 1][RIGHT] + stage[i - 2][RIGHT];
        stage[i][RIGHT] = stage[i - 1][LEFT] + stage[i - 2][LEFT];
    }
    cout << stage[39][RIGHT] << endl;
    return 0;
}