记录编号	32768	评测结果	AAAWWWWWWW
题目名称	分裂	最终得分	30
用户昵称	fanzeyi	是否通过	未通过
代码语言	C	运行时间	2.062 s
提交时间	2011-11-08 12:31:09	内存使用	0.55 MiB

/*
ID: fanzeyi1
LANG: C
TASK: mushroom 
*/
/*
 * =====================================================================================
 *
 *       Filename:  mushroom.c
 *        Version:  1.0
 *        Created:  11/08/2011 09:43:17 AM
 *       Revision:  none
 *       Compiler:  gcc
 *         Author:  Zeray Fan, fanzeyi1994[at]gmail.com
 *        Company:  http://www.fanhe.org/
 *
 * =====================================================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned long long mushroom[2][20000]; 

int main(void) {
    FILE *fin = fopen("mushroom.in","r");
    FILE *fout = fopen("mushroom.out", "w");
    int i; 
    int n;
    int max;
    int tmp; 
    int time;
    unsigned long long result; 
    fscanf(fin, "%d", &n); 
    max = 2; 
    memset(mushroom, 0, sizeof(mushroom)); 
    mushroom[0][2] = 1; 
    for( time = 0 ; time < n ; time++ ) {
        tmp = max; 
        memset(mushroom[(time&1)^1], 0, sizeof(mushroom[0])); 
        for( i = 1 ; i <= max ; i++ ) {
            if(i == 1 && mushroom[time&1][i]) {
                mushroom[(time&1)^1][2] += mushroom[time&1][1]; 
                continue; 
            }
            if(mushroom[time&1][i]) {
                mushroom[(time&1)^1][i+1] += mushroom[time&1][i]; 
                mushroom[(time&1)^1][i-1] += mushroom[time&1][i]; 
                if(i + 1 > tmp) {
                    tmp = i + 1; 
                }
            }
        }
        max = tmp; 
    }
    result = 0; 
    for( i = 1 ; i <= max ; i++ ) {
        result = result + mushroom[(n&1)^1][i]; 
    }
    fprintf(fout, "%llu\n", result); 
    return 0;
}