logo AlgoBeat OnlineJudge
登录 注册

#215436. [ROI 2012 Day 1] calendar 古代日历

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

翻译来源:loj #5458. 「ROI 2012 Day 1」古代日历


众所周知,2012 年人类对古代日历表现出了极大的关注。尤其令人感兴趣的是那些并未在 2012 年结束的日历。鞑靼斯坦的考古学家在这方面取得了惊人的发现。他们在古代墓葬中发现了一块矩形石板,经过破译保存下来的符号后,将其记录为一个包含 行、每行 个十进制数字的表格。然而,石板未能完全破译,因为部分数字已经磨损。表格中丢失的数字用符号 * 替代。

考古学家认为,这块石板是一个古代日历,其中的 位数字表示某个时间段内连续的日子编号。第一个数字是该时间段第一天的编号,随后每个数字比前一个数字大 。根据这个日历,世界末日并不存在,在由 组成的日子编号之后,紧接着的是由 组成的日子编号。

你需要编写一个程序,恢复丢失的数字,使得表格中从第二行开始的每个数字比前一行大 ,并输出找到的日历中第一天的编号。

输入格式

输入文件的第一行包含两个自然数 ,分别表示表格的行数和每行的长度。

接下来有 行,每行包含 个字符,仅由十进制数字 和符号 * 组成。

输出格式

输出文件应包含一行,由 个数字组成,表示日历中第一天的编号。如果存在多种恢复方式,可以输出任意一种。保证至少存在一种恢复方式。

样例

样例输入 1

1 2
23

样例输出 1

23

样例输入 2

3 3
1**
*1*
**1

样例输出 2

109

样例输入 3

2 3
9**
00*

样例输出 3

999

样例输入 4

3 4 
****
*0**
01**

样例输出 4

0098

数据范围与提示

详细子任务附加限制及分值如下表所示:

子任务 分值 附加限制 说明
,每列至少有一个保存下来的数字 需通过该子任务所有测试点才可获得分数
,至少有一列只包含* 每个测试点独立评分
需通过该子任务所有测试点才可获得分数