Дендрохронология

Дендрохронология – метод, в основе которого лежит закон природы, согласно которому каждый год толщина дерева увеличивается на одно кольцо. Толщина каждого кольца зависит от погоды в год образования кольца. У деревьев, растущих в одном и том же месте и климате толщина колец примерно одинакова. По числу колец можно определить возраст дерева, а по толщине колец – погодные условия каждого года, в который это дерево росло.

Используя «перекрестную датировку», можно построить дендрохронологическую шкалу путем увязывания воедино следующих друг за другом поколений деревьев, годы жизни которых перекрываются. Именно так возможно определить погодные условия от некоторого времени до настоящего момента. А на основании построенной шкалы можно датировать те или иные деревянные предметы, сохранившиеся с давних лет.

Однажды, в одном древнем городе, основанном в болотистой местности, археологи обнаружили N слоев мостовых, положенных один над другим и состоящих из отлично сохранившихся бревен. При этом первый слой был положен в момент основания города, а последний – в текущем году. Определив толщину колец бревен для каждого слоя мостовой, они задались вопросом: каков возраст этого города?

Ваша задача – помочь археологам вычислить возраст города по имеющимся данным.

Входные данные

Первая строка входного файла INPUT.TXT содержит натуральное число N – количество слоев мостовых. Далее следует N строк, описывающих в хронологическом порядке дендрохронологическую шкалу для каждого бревна, взятого из отдельного слоя мостовой. Каждая строка состоит из цифр от 1 до 3, соответствующих толщине годовых колец в миллиметрах описываемого дерева от первого до последнего года его жизни. Суммарная длина всех строк не превышает 10⁶. Гарантируется, что дерево, из которого получено бревно следующего уровня, начало расти не раньше, чем дерево, из которого получено бревно предыдущего уровня. Аналогично гарантируется, что дерево, из которого получено бревно следующего уровня, было срублено не раньше, чем дерево, из которого получено бревно предыдущего уровня. Также известно, что годы жизни деревьев соседних уровней перекрываются. При неоднозначном определении общего периода жизни для деревьев смежных слоев следует выбирать максимально возможный диапазон.

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное целое число – возраст города.

Пример

Система оценивания

Решения, работающие только в тех случаях, когда общий период жизни деревьев в смежных слоях составляет не более 10 лет, будут оцениваться в 40 баллов.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]