View Code of Problem 60

#include<stdio.h>

typedef long long ll;
ll c[42][42];

void init()
{
    int i,j;
    for(i = 0;i <= 41;i ++)
        for(j = 0;j <= 41;j ++)
            c[i][j] = 0;
    for(i = 0;i < 42;i ++) {c[i][0] = 1;}
    for(i = 1;i <= 41;i ++)
        for(j = 1;j <= i;j ++)
            c[i][j] = c[i-1][j-1] + c[i-1][j];
    /*
    for(i = 1;i <= 41;i ++)
        for(j = 1;j <= i;j ++)
            printf("c[%d][%d] = %lld ",i,j,c[i][j]);
            */
}
ll solve(int n)
{
    int i,j;
    ll ans = 0;
    if(n == 1)
        ans = 2;
    else{
        for(i = 0;i <= (n%2 == 0?n/2:n/2+1);i ++){
            ans += c[n-i+1][i];
           // printf("ans = %lld\n",ans);
        }
    }
    return ans;
}
int main(void)
{
    ll ans,cas,n,t=1;
    scanf("%lld",&cas);
    init();
    while(cas --)
    {
        scanf("%lld",&n);
        ans = solve(n);
        printf("Scenario #%lld:\n%lld\n\n",t ++,ans);
    }
}