3897 - 生产线

题目描述

工厂有一条生产配件的生产线,专门为工厂的某型号的汽车生产配件。

该生产线每次可以生产 N 个配件,配件的编号为 1 \sim N,生产配件的顺序也严格按照 1 \sim N 的顺序进行。

生产线生产一个配件需要 1 小时,每小时只能生产 1 个配件。某些编号的配件,在生产时,要使用一些其他配件作为辅助。每个配件生产出来之后,需要经过 3 个小时的完全冷却,才能在下一个小时作为其他配件的加工辅助。由于配件生产顺序严格按照 1 \sim N,因此如果 X 号配件需要 Y 号配件辅助,可以确保 X \gt Y

比如:如果要生产 2 个配件,编号分别为 1,2,如果 2 号配件不需要 1 号配件辅助,那么两个配件生产完毕共需 2 小时。如果 2 号配件需要 1 号配件的辅助,那么在第 1 小时结束,1 号配件生产完毕,需要额外增加 3 个小时的冷却时间,因此 2 号配件需要在第 5 个小时结束才能被生产出来,两个配件生产完需要 5 小时,产生了额外的 3 小时的冷却时间

再比如:如果要生产 5 个配件,只有编号为 5 的配件需要编号为 1 的配件辅助,总生产时间还是 5 小时,因为生产 5 号配件时,1 号配件已经冷却完毕,不需要产生额外的冷却时间

现给出每个配件生产需要其他哪些配件辅助的所有数据,请问 N 个配件生产完毕,一共产生了多少小时的额外冷却时间?

输入

1 行读入一个整数 N,代表配件总数。

接下来 N 行,每行有 3 个整数,如果接下来第 i 行的第 j 个整数为 1 ,表示配件 i 生产时,需要配件 i-j 的辅助。

测试数据确保不会出现 i \le j 时, 第 i 行第 j 列的值为 1 的情况。

输出

输出一个整数,代表 N 个配件生产完毕,一共产生了多少小时的额外冷却时间

样例

输入

3
0 0 0
1 0 0
1 1 0

输出

6

输入

3
0 0 0
1 0 0
0 1 0

输出

3

输入

8
0 0 0
0 0 0
0 1 0
0 1 0
1 1 1
0 0 1
1 1 1
0 1 1

输出

8
说明

样例 1 解释

1 行读入 N=3

接下来的 3 行:

2 行第 1 个整数为 1,说明 2 号配件需要 2-1=1 号配件的辅助。

3 行前 2 个整数为 1,说明 3 号配件需要 3-1=2 号和 3-2=1 号配件的辅助。

因此每个小时生产线的工作记录如下:

1 个小时,生产 1 号配件。

2 \sim 4 个小时,等待 1 号配件冷却。

5 个小时,生产 2 号配件。

6 \sim 8 个小时,等待 2 号配件冷却。

9 个小时生产 3 号配件。

一共产生了 6 小时的额外冷却时间。

数据范围

对于 20\% 的数据,1 \le N \le 20,测试数据只有一个配件要使用其他配件作为生产辅助的情况。

对于 100\% 的数据, 1 \le N \le 100

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题