/*
 * 方法名称：迭代法（循环递推）
 * 原理：基于数列的边界条件（f(1)=0、f(2)=1、f(3)=1）和递推公式（f(n)=f(n-1)+2f(n-2)+f(n-3)），
 *       通过循环手动维护前三项的结果值，逐步迭代推进，直接计算出第n项结果，无递归调用，仅依赖循环变量更新。
 * 时间复杂度：O(n)，循环执行n-3次（n≥4），单次循环操作均为常数时间。
 * 空间复杂度：O(1)，仅使用固定个数的整型变量，不额外占用与n相关的空间。
 * 适用场景：1. 所有存在明确递推关系的数列计算；2. n较大时（无栈溢出风险），追求极低空间开销；
 *          3. 初学者易理解、易实现、易调试的场景；4. 对代码运行效率要求较高且需避免递归栈开销的场景。
 */
#include <stdio.h>

int main() {
    int n;
    if (scanf("%d", &n) != 1 || 1 > n || n > 20) {
        return 1;
    }
    if (n > 3) {
        // 初始化递推所需的前三项值，对应f(n-3)、f(n-2)、f(n-1)（初始为f(1)、f(2)、f(3)）
        int a = 0, b = 1, c = 1;
        // 循环递推，从第3项推进到第n-1项，最终c为第n项结果
        for (int i = 3; i < n; i += 1) {
            // 临时保存当前f(n-1)的值，用于后续更新b
            int r = c;
            // 核心递推公式：计算当前第i+1项的值（即下一个c）
            c = c + 2 * b + a;
            // 更新前三项：a承接原f(n-2)，b承接原f(n-1)
            a = b;
            b = r;
        }
        printf("%d", c);
    }
    else if (n > 1) {
        // n=2、3，对应边界条件f(2)=1、f(3)=1
        printf("1");
    }
    else {
        // n=1，对应边界条件f(1)=0
        printf("0");
    }
    return 0;
}

/*
 * 方法名称：记忆化递归法（递归+缓存）
 * 原理：利用递归函数贴合数列的数学递推公式，同时通过全局数组作为缓存容器，保存已计算完成的子问题结果，
 *       当再次需要该子问题结果时，直接从缓存中获取，避免重复递归计算，兼顾递归的简洁性和高效性。
 * 时间复杂度：O(n)，每个子问题（f(1)到f(n)）仅计算一次，后续直接命中缓存返回，无重复运算。
 * 空间复杂度：O(n)，主要开销为缓存数组（长度n+1）和递归调用栈（深度最大为n-3），均与n线性相关。
 * 适用场景：1. 存在大量重复子问题的递推数列计算；2. 追求代码简洁直观、与数学公式高度吻合的场景；
 *          3. n不宜过大（通常n≤1000，避免递归栈溢出）；4. 后续需修改递推公式，希望降低代码修改成本的场景。
 */
#include <stdio.h>
#include <string.h>

// 全局数组：缓存容器，存储f(1)到f(20)的结果，下标与n直接对应
int A[21];

// 记忆化递归函数，计算并返回第n项的结果
int a(int n) {
    // 缓存命中判断：若A[n]>-1，说明已计算过，直接返回缓存结果
    if (A[n] > -1) {
        return A[n];
    }
    // 缓存未命中：按递推公式递归计算，并将结果存入缓存（更新缓存）
    A[n] = a(n - 1) + 2 * a(n - 2) + a(n - 3);
    return A[n];
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || 1 > n || n > 20) {
        return 1;
    }
    // 将缓存数组A全部初始化为-1（0xff对应int类型的-1），标记未计算的子问题
    memset(A, 0xff, 84);
    // 初始化边界条件（递归锚点），存入缓存，作为递归的终止条件
    A[1] = 0, A[2] = A[3] = 1;
    // 调用递归函数，输出第n项结果
    printf("%d", a(n));
    return 0;
}

/*
 * 方法名称：闭式公式法（通项公式+复数运算）
 * 原理：针对三阶线性齐次常系数递推数列，通过特征方程法推导得到数列的闭式通项公式，
 *       利用高精度浮点运算和复数运算实现通项公式的计算，直接一步到位得到第n项结果，无需循环或递归。
 * 时间复杂度：O(1)，所有计算均为常数时间的数***算，与n的大小无关，计算效率最优。
 * 空间复杂度：O(1)，仅使用固定个数的高精度浮点变量和复数变量，不占用与n相关的额外空间。
 * 适用场景：1. 存在明确闭式通项公式的线性齐次递推数列计算；2. 对计算效率要求极高，追求常数时间复杂度的场景；
 *          3. n在高精度浮点类型（long double）的精度范围内（避免浮点误差累积）；4. 无需理解递推过程，仅需快速获取结果的场景。
 */
#include <stdio.h>
#include <math.h>
#include <complex.h>

int main() {
    int n;
    if (scanf("%d", &n) != 1 || 1 > n || n > 20) {
        return 1;
    }
    // 初始化特征方程求解得到的核心常量，长双精度浮点型减少计算误差
    long double a = cbrtl(19 + sqrtl(33)), b = cbrtl(19 - sqrtl(33));
    // 定义三次单位根（复数），用于处理特征方程的共轭复根
    long double complex w = sqrtl(3) / 2 * I - 0.5, m = w * w;
    // 转换n为长双精度型，保证复数幂运算的参数类型匹配
    long double complex N = n;
    // 计算特征方程的三个根（r1为实根，r2、r3为共轭复根）
    long double complex r1 = (1 + a + b) / 3, r2 = (1 + w * a + m * b) / 3, r3 = (1 + m * a + w * b) / 3;
    // 计算通项公式的权重系数，平衡三个幂次项的贡献
    long double complex c1 = 1 / ((r2 - r1) * (r3 - r1)), c2 = 1 / ((r1 - r2) * (r3 - r2)), c3 = 1 / ((r3 - r1) * (r3 - r2));
    // 核心：执行通项公式计算，提取实部、四舍五入修正误差、转换为整型输出
    printf("%d", (int)round(creal(c1 * cpowl(r1, N) + c2 * cpowl(r2, N) + c3 * cpowl(r3, N))));
    return 0;
}

//递归思想很快，但费时间
#include <stdio.h>

int Fun(int num)
{
    if(num==1)
    {
        return 0;
    }
    else if(num>=2&&num<=3){
        return 1;
    }
    else 
        return Fun(num-3)+2*Fun(num-2)+Fun(num-1);
}

int main() {
    int num=0;
    scanf("%d",&num);
    int ret = Fun(num);
    printf("%d\n",ret);
    return 0;
}

递归写法-裸递归

#include <stdio.h> 
int solution(int n)
{
    if (n < 4)
    {
         return n == 1 ? 0 : 1;
    }
   
    return solution(n - 3) + 2 * solution(n - 2) + solution(n - 1);
}
int main() {
   
    int n = 0;
    scanf("%d", &n);
    printf("%d", solution(n));
    return 0;
}

#include <stdio.h>
#include <stdint.h>

#define MAX 20
#define INVALID -1

uint32_t memo[MAX + 1];

uint32_t solution(uint32_t n)
{
    if (n < 4)
    {
         return n == 1 ? 0 : 1;
    }

    if (memo[n] != INVALID)
    {
        return memo[n];         // 已经计算过，直接返回
    }

    memo[n] = solution(n - 3) + 2 * solution(n - 2) + solution(n - 1);

    return memo[n];
}
int main() {
    
    uint32_t n = 0;

    // 初始化备忘录
    for (int i = 0; i <= MAX; i++)
    {
        memo[i] = INVALID;
    }

    scanf("%u", &n);

    printf("%u", solution(n));

    return 0;
}

#include <stdio.h>
#include <stdint.h>

uint32_t solution(uint32_t n)
{
    if (n < 4)
    {
        return n == 1 ? 0 : 1;
    }

    int cur = 0;    // 当前计算出的 An 值
    int a1 = 0, a2 = 1, a3 = 1; // a1 到 a3 类比于指针，初始分别指向数列的前 3 项

    for (uint32_t i = 4; i <= n; i++)
    {
        // 计算出当前 An 的值，即 Ai 的值（当 n = i 时，An 的值）
        // 此时的 cur 表示着 a4 指针
        cur = a1 + 2 * a2 + a3;

        // 指针移动
        a1 = a2;
        a2 = a3;
        a3 = cur;
    }

    return cur;
}
int main() {
    
    uint32_t n = 0;

    scanf("%u", &n);

    printf("%u", solution(n));

    return 0;
}