[NOI1996]三角形灯塔

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file lighthouse.in Output file lighthouse.out

【题目描述】

有一个N行(0<N<=50)的三角形灯塔,它的第1行有1个灯,第2行有2个灯,…,第N行有N个灯。我们用(i,j)表示从上至下第i行,从左至右第j个灯。

每个灯有明、暗两种状态,第i行任意一个灯(i,j)的状态由下一行的两个灯(i+1,j)和(i+1,j+1)的状态决定。具体的规则如下表所示:




(i+1,j)的状态 (i+1,j+1)的状态 (i,j)的状态

请你编一个程序,从已知的某几个灯的状态出发,推出最底一行N个灯的所有可能的状态总数。

【输入格式】

第一行为一个整数N(1<=N<=50)

接下来有若干行,每行有三个整数i,j,k(1<=j<=i<=N),表示已知灯(i,j)的状态为k(0表示不亮,1表示亮)

【输出格式】

若问题无解,则输出“No Answer!”;否则输出可能的状态总数。

【样例输入】

4
1 1 1
3 2 1
4 2 1

【样例输出】

2

【来源】

NOI1996,day1