Problem4358--火柴棒等式

4358: 火柴棒等式

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

给你 $n$ 根火柴棍,你可以拼出多少个形如 $A+B=C$ 的等式?等式中的 $A,B,C$ 是用火柴棍拼出的整数(若该数非零,则最高位不能是 $0$)。用火柴棍拼数字 $0 \sim 9$ 的拼法如图所示:

注意:
  1. 加号与等号各自需要两根火柴棍。
  2. 如果 $A \neq B$,则 $A+B=C$ 与 $B+A=C$ 视为不同的等式 $(A,B,C>=0)$ 。
  3. $n$ 根火柴棍必须全部用上。

Input

一个整数 $n\ (n \leq 24)$。

Output

一个整数,能拼成的不同等式的数目。

Sample 1 Input

14

Sample 1 Output

2
$2$ 个等式为 $0+1=1$ 和 $1+0=1$。

Sample 2 Input

16

Sample 2 Output

9
$9$ 个等式为:
$0+4=4\\
0+11=11\\
1+10=11\\
2+2=4\\
2+7=9\\
4+0=4\\
7+2=9\\
10+1=11\\
11+0=11$

HINT

相同题目:洛谷P1149

Source/Category

基础算法 4.11.递归