Задача №111224. Древний календарь
Как известно, в 2012 году человечество с повышенным вниманием относится к древним календарям. Особый интерес представляют те из них, которые не заканчиваются 2012 годом. Потрясающее открытие в этом направлении сделано археологами Татарстана. В древних захоронениях oни обнаружили прямоугольную табличку, которая после расшифровки сохранившихся знаков была записана в виде таблицы, состоящей из N строк по M десятичных цифр в каждой. Но полностью расшифровать табличку не удалось, так как некоторые цифры стерлись. Утраченные цифры в таблице были заменены символами «*». По мнению археологов, найденная табличка представляет собой древний календарь, а записанные в ней M-значные числа являются номерами последовательных дней некоторого периода. Первое число является номером первого дня этого периода, а каждое следующее число на единицу больше предыдущего. По этому календарю конец света отсутствует, и после дня, обозначаемого с помощью M девяток, следует номер дня из M нулей. Требуется написать программу, которая восстанавливает утраченные цифры так, чтобы число в каждой строке таблицы, начиная со второй, было на единицу больше предыдущего, и выводит номер первого дня в найденном календаре.
В первой строке входного файла записаны натуральные числа N и M – количество строк в таблице и длина каждой строки соответственно (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000, M × N ≤ 100 000). Далее следуют N строк по M символов в каждой, состоящих только из десятичных цифр от 0 до 9 и символов «*».
Выходной файл должен содержать одну строку, состоящую из M цифр – номер первого дня календаря. Если вариантов восстановления несколько, можно вывести любой из них. Гарантируется, что хотя бы один способ восстановления существует.
Данная задача содержит три подзадачи.
- (оценивается в 40 баллов) 1 ≤ N ≤ 1000, 1 ≤ M ≤ 100. В этой подзадаче исходные данные таковы, что в каждом столбце таблицы есть, по крайней мере, одна сохранившаяся цифра. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
- (оценивается в 30 баллов) 1 ≤ N ≤ 1000, 1 ≤ M ≤ 100. В этой подзадаче хотя бы один столбец содержит только символы «*». Каждый тест в этой подзадаче оценивается отдельно.
- (оценивается в 30 баллов) 1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000, M × N ≤ 100 000. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
1 2 23
23
3 3 1** *1* **1
109
2 3 9** 00*
999
3 4 **** *0** 01**
0098