球迷购票问题

题目背景

盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。 按售票处规定,每位购票者限购一张门票,且每张票售价为50元。在排成长龙的球迷中有N个人手持面值50元的钱币,另有N个人手持面值100元的钱币。假设售票处在开始售票时没有零钱。试问这2N个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。

题目描述

例如当n=2是,用A表示手持50元面值的球迷,用B表示手持100元钱的球迷。则最多可以得到以下两组不同的排队方式,使售票员不至于找不出钱。 第一种:A A B B 第二种:A B A B [编程任务] 对于给定的n (0≤n≤20),计算2N个球迷有多少种排队方式,可以使售票处不至于找不出钱。

输入输出格式

输入格式


一个整数,代表N的值

输出格式


一个整数,表示方案数

输入输出样例

输入样例 #1

2

输出样例 #1

2

说明

必开QWORD 测试:N=15 回溯:1秒(超时) 模拟栈:大于10分钟 递归算法:1秒(超时) 动态规划:0 MS 组合算法:16 MS