分数: 1000 点
问题陈述
我们将举办石头剪刀布锦标赛 N 人。参与者被称为 Person 1, 人 2, \ldots, 人 N。 对于任何两个参赛者来说,他们之间的比赛结果是预先确定的。 该信息用正整数表示 A_{i,j} ( 1 \leq j < i \leq N )如下:
- If A_{i,j} = 0, 人 j 击败人 i.
- If A_{i,j} = 1, 人 i 击败人 j.
比赛进行如下:
- 我们会安排 N 参与者连续,按人的顺序 1, 人 2, \ldots, 人 N 从左到右。
- 我们将随机选择该行中连续的两个人。他们将进行一场比赛,我们会将失败者从行中删除。 我们将重复这个过程 N-1 次,最后剩下的人将被宣布为冠军。
找出有可能成为冠军的人数。
约束
- 1 \leq N \leq 2000
- A_{i,j} is 0 or 1.
输入
输入由标准输入按以下格式给出:
N
A_{2,1}
A_{3,1}A_{3,2}
:
A_{N,1}\ldotsA_{N,N-1}
输出
打印有可能成为冠军的人数。
示例输入 1
3 0 10
示例输出 1
2
人 1 击败人 2, 人 2 击败人 3 和人 3 击败人 1。 如果人 1 和人 2 进行第一场比赛,Person 3 将成为冠军。 如果人 2 和人 3 进行第一场比赛,Person 1 将成为冠军。
示例输入 2
6 0 11 111 1111 11001
示例输出 2
3