Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 2 сек. Память: 32 Мб Сложность: 50%)

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

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

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

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

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

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

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

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

Пример

INPUT.TXTOUTPUT.TXTПояснение
14
123123123
3123111321
13212212
212331
13 123123123
.....3123111321
...........13212212
................212331
(на основании этих данных можно определить дендрохронологическую шкалу для последних 22 лет)

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

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


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2005 / 2006
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 A. Снежинка Коха
 B. Голосование
 C. Дендрохронология
 D. Числа Фибоначчи
 E. Крестики-нолики

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru