← 返回题目列表

AtCoder · m_solutions2019_f

F. 随机锦标赛

中文机器翻译题面 查看原题

分数: 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