第一课堂
Current course
Participants
General
Topic 2
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
[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