3866. OLED

单点时限: 2.5 sec

内存限制: 256 MB

OLED 是一种新兴的显示技术。相比于传统 LED 屏幕,可以实现更高的显示亮度、对比度,同时更轻更薄。然而发展至今,OLED 仍然有一个根源性的缺陷:由于 OLED 的每一个像素点单独发光,所以发光时常更长、发光亮度更大的像素,老化速度更快。因此,如果屏幕长时间显示静止的画面,各个像素由于衰减速度不一,时间一长,画面的纹路就好像被烙在了屏幕上。这个现象俗称”烧屏”。

由于现在 OLED 技术的发展,屏幕寿命更加持久,因此烧屏现象不再那么明显。此外,手机厂商也利用了一些软件方面的技术缓解烧屏问题。

屏保(熄屏图像)由于是静止图像,且显示时常非常长,自然是烧屏的重灾区。如今的手机厂商往往会采取以下技术方案:每过一定时间,随机地平移屏保图像。这样,各个像素的发光时常就会更加均匀,不易引发烧屏。

可是,即便如此,烧屏的隐患也没有根本去除。理论上说,虽然屏保图像的位置会移动,但是屏幕上的所有像素的发光时常也不完全均等。只要时间足够长,烧屏依然会发生。Cuber QQ 非常好奇他的手机屏幕在很久以后烧屏情况如何。因此他把他的屏保图像和屏幕尺寸告诉了你,请求出期望的烧屏情况。

为了简化问题,我们规定如下。

屏幕是一个 $a$ 行 $b$ 列(下简称 $a \times b$)的矩阵。屏保图像是一个 $n \times m(1\le n\le a,1\le m\le b)$ 的黑白图像。$1$ 表示白色,$0$ 表示黑色。当屏保图像显示在屏幕上时,白色对应的像素发光,屏幕上其余的所有像素不发光 (显然, 屏保至少有一点发光, 也就是图像中至少有一个 $1$)。

每分钟,这个屏保图像会等概率地随机出现在屏幕上的任何一个合法位置(合法位置满足:屏保图像上的每一个像素不超过屏幕边界,图像不缩放,不旋转)。因此学过数学的同学肯定会发现,屏幕一共有 $(a-n+1)\cdot(b-m+1)$ 种等概率的显示状态。

Cuber QQ 发现,一个像素的衰减系数和它的发光时长成正比。为了方便后续研究,Cuber QQ 规定屏幕上衰减程度最大(也就是发光时长最长)的像素的衰减系数为 $100$,其余像素的衰减系数以此为基准可以相应得出。

给定屏幕尺寸和屏保图案,请你求出经过足够长的时间,每一个像素期望的衰减系数。

输入格式

第一行 $n,m,a,b$ ($1 \le a \le 3840$, $1 \le b\le 2160$, $1 \le n \le a$, $1 \le m \le b$)。

接下来一个 $n\times m$ 的 $01$ 矩阵表示屏保图案, 且矩阵中至少有一个 $1$。

输出格式

输出一个 $a\times b$ 的整数矩阵表示每个像素的衰减系数的整数部分 (即将衰减系数从小数向下取整)。根据题目描述,矩阵中的最大值显然为 $100$。

样例

Input
1 2 4 3
0 1 
Output
0 100 100 
0 100 100 
0 100 100 
0 100 100 
Input
3 2 6 7
1 1 
0 0 
0 1 
Output
33 66 66 66 66 66 33 
33 66 66 66 66 66 33 
33 100 100 100 100 100 66 
33 100 100 100 100 100 66 
0 33 33 33 33 33 33 
0 33 33 33 33 33 33 

232 人解决,276 人已尝试。

256 份提交通过,共有 714 份提交。

2.4 EMB 奖励。

创建: 9 月,1 周前.

修改: 9 月,1 周前.

最后提交: 1 周,6 天前.

来源: N/A

题目标签