开始 2022-02-12 07:40:00

2022年寒假第二段提升日

结束 2022-02-26 11:40:00
比赛已经结束
当前 2024-11-20 00:32:26

C. 编译器

描述

在汇编语言程序中,程序是由多句汇编语句组成的,每句汇编语句会从寄存器中读一些数据(可能不读)和向寄存器中写一些数据(可能不写)。但由于CPU流水线式的架构,一条语句A写入寄存器的数据若想被语句B读到,则语句B和A之间至少要间隔三条语句,否则B将读到该寄存器中的老数据而不是A刚刚写入的数据,这被称为寄存器的先写后读相关问题。

例如,第一条语句写入了十号寄存器一个数据,若想写一个读取十号寄存器中数据的语句,则该语句最快也要等到第五句才可以(因为此时两条语句才恰好间隔三句)。

解决先写后读相关问题往往可以使用插入空操作(空操作也是一种汇编语句,该语句什么都不做,只起到占位的作用)的方法,即填充一些什么都不做的语句到原程序中。例如,现在第一条语句写入了八号寄存器、第二条语句读取了八号寄存器,因此存在对八号寄存器的先写后读相关问题,可以通过在之中插入三句空语句来解决该问题,即原程序在插入后变为:原第一条语句、空语句、空语句、空语句、原第二条语句。

现在,给出一个原有n个语句的汇编程序,并给出程序中语句之间发生先写后读相关的情况,请你求出最少添加多少个空语句可以使得该程序完全不存在任何先写后读相关问题。

输入

第一行,包含一个整数n,表示程序原有语句总数。

接下来n行,每行有3个数字,每个均为0或1.第i行的第j个数字若为1表示第i行语句与第i-j行语句发生了先写后读关系;若为0表示没有先写后读关系。

对于100%的数据:

3 \le n \le 100

且,第一行均为0,第二行第2、3个均为0,第三行第3个为0。

输出

一个整数,表示为使每个先写后读得到正确结果至少需要添加多少条空语句。

样例

输入

4
0 0 0
1 0 0
0 1 0
0 0 1

输出

3

提示

样例中第2、3、4条语句与第1条语句发生先写后读关系,在第一条语句后添加3行空语句即可。


提交

登录

注册
时间限制 1000 毫秒
内存限制 128 MB
提交