[NOI1996]三角形灯塔

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 lighthouse.in 输出文件 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