/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
N 人の参加するじゃんけん大会を行います。 参加者は人 1, 人 2, \ldots, 人 N と呼ばれます。 どの 2 人についてもその 2 人がじゃんけんをしたときにどちらが勝利するかが事前に決まっています。 この情報は正の整数 A_{i,j} ( 1 \leq j < i \leq N ) によって表され、
- A_{i,j} = 0 のとき、人 i は人 j に負けること
- A_{i,j} = 1 のとき、人 i は人 j に勝つこと
をそれぞれ表します。
大会は次のようにして行われます。
- N 人の参加者を人 1, 人 2, \ldots, 人 N の順に横一列に並べる。
- 列で連続している 2 人をランダムに選んで、その 2 人で試合を行い、負けた人を列から外す。 これを N-1 回繰り返し、最後に残った 1 人を優勝者とする。
優勝する可能性のある人の人数を求めてください。
制約
- 1 \leq N \leq 2000
- A_{i,j} は 0 または 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 が試合をすると人 3 が優勝し、 最初に人 2 と人 3 が試合をすると人 1 が優勝します。
入力例 2
6 0 11 111 1111 11001
出力例 2
3
Score : 1000 points
Problem Statement
We will host a rock-paper-scissors tournament with N people. The participants are called Person 1, Person 2, \ldots, Person N. For any two participants, the result of the match between them is determined in advance. This information is represented by positive integers A_{i,j} ( 1 \leq j < i \leq N ) as follows:
- If A_{i,j} = 0, Person j defeats Person i.
- If A_{i,j} = 1, Person i defeats Person j.
The tournament proceeds as follows:
- We will arrange the N participants in a row, in the order Person 1, Person 2, \ldots, Person N from left to right.
- We will randomly choose two consecutive persons in the row. They will play a match against each other, and we will remove the loser from the row. We will repeat this process N-1 times, and the last person remaining will be declared the champion.
Find the number of persons with the possibility of becoming the champion.
Constraints
- 1 \leq N \leq 2000
- A_{i,j} is 0 or 1.
Input
Input is given from Standard Input in the following format:
N
A_{2,1}
A_{3,1}A_{3,2}
:
A_{N,1}\ldotsA_{N,N-1}
Output
Print the number of persons with the possibility of becoming the champion.
Sample Input 1
3 0 10
Sample Output 1
2
Person 1 defeats Person 2, Person 2 defeats Person 3 and Person 3 defeats Person 1. If Person 1 and Person 2 play the first match, Person 3 will become the champion. If Person 2 and Person 3 play the first match, Person 1 will become the champion.
Sample Input 2
6 0 11 111 1111 11001
Sample Output 2
3