/ Vijos / 题库 /

飞船控制站(csapc)

飞船控制站(csapc)

描述

“神州七号”飞船已经圆满发射成功了,你可知道飞船的顺利运行离不开地面对其的测控吗?因而必须保证飞船运行的轨道被测控站的雷达所全部覆盖,才能正常接受和传输信号。而由于测控站所控制的范围越小,信号接收情况越好,技术难度也越低。所以我们希望在覆盖整个轨道的前提下,使得测控站所需控制的范围越小越好。由于条件限制,最多只能建立K个测控范围相同的测控站,而且并不是任何位置都可以建立测控站的,所以需要找出一种方案,使得所需测控的范围尽量小。虽然离真正的模型还有一定差距,但喜欢编程的你当然对此问题跃跃欲试了。

为了你的方便,已经帮你把地球抽象展开成一个N*2M的平面矩阵(N为奇数)。其中前M列是东半球,后M列是西半球,最中间的一行为赤道。为了简化问题,飞船的轨道可以看作是在一条穿越东西半球的经线上空(虽然实际并非如此),在此矩阵表示为第I列和第I+M列(1<=I<=M)两端对接形成的一个环。矩阵的每一个格子中可以建立一个监测站,但某些格子除外(比如其他国家的领土或是条件恶劣的地区)。假设测控半径为R,则每个测控站的控制范围可以向上向下各延伸R个格子,即总长度为2R+1的区间。测控范围的重叠并不会相互影响,并且显然有R>=0且2R+1<=N(因为地球是圆的,测控范围最多只能是一个半球)。

由于飞船有M条可选轨道,所以需要你计算出对于每条轨道,最小的测控半径是多少。注意由于控制的需要,对于任意一条轨道,在东半球的赤道上都必须建立一个测控站,并且保证在东半球的赤道上建站不会有限制。

格式

输入格式

输入的第一行为三个正整数N,M,K表示矩阵的大小以及测控站的数量。保证有(2<=N,M<=1000,2<=K<=2N,N为奇数)。接下来N行,每行2M个字符,如果是1则表示可以放置测控站,否则为0表示无法放置。(保证中间一行的前M个字符一定为1)

输出格式

输出包含M行,每行包含一个正整数,第I行表示第I条轨道所需最小的测控半径R为多少(保证必然有解),轨道从左到右依次编号。

样例1

样例输入1

5 2 4   
0110
0000
1100
0011
1000

样例输出1

1
2

提示

对于轨道1:从第一行第一列开始向下可以展开为0010101001(首尾相连)
对于轨道2:从第一行第二列开始向下可以展开为1010001000(首尾相连)
两条轨道均把可选点全部建站即可。

数据规模:
对于30%的数据,有N,M<=15
对于60%的数据,有N,M<=100

对于100%的数据,有N,M<=1000

信息

ID
1475
难度
8
分类
贪心 点击显示
标签
递交数
181
已通过
27
通过率
15%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

第一届海峡两岸青少年程序设计竞赛