Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 6 задач <---
Источники --> Командные олимпиады --> Командные чемпионаты школьников Санкт-Петербурга по программированию
    1999(5 задач)
    2000(7 задач)
    2001(8 задач)
    2002(8 задач)
    2003(9 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(10 задач)
    2008(9 задач)
    2009(10 задач)
    2010(10 задач)
    2011(9 задач)
    2012(10 задач)
    2013(10 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: << 1 2 Отображать по:
#3407
Вычислительная ихтиология
  
Темы: [Куча]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Игорь работает младшим лаборантом в НИИ ихтиологии. Ему вверены \(n\) аквариумов, стоящих в ряд, в каждом из которых живет колония рыбок гуппи. Про каждую колонию заранее известна ее численность.

В лабораторных условиях НИИ ихтиологии колония рыбок гуппи растет по следующему правилу: достигнув популяции в \(f\) рыбок, колония живет в течении \(max(1000 - f, 1)\) секунд, после чего на свет появляется новая рыбка. От начального момента времени до рождения первой рыбки колония размера \(f\) также ждет \(max(1000 - f, 1)\) секунд.

Например, колония с начальным размером 996 будет размножаться следующим образом:

момент времениразмер колониивремя до очередной рыбки
09964
49973
79982
99991
1010001
1110011
1210021
.........

Появление на свет каждой новой рыбки Игорь должен фиксировать в специальном журнале. Будем считать, что запись он делает мгновенно, но при этом он должен в момент рождения новой рыбки находиться рядом с аквариумом, в котором это произошло.

На перемещение от одного аквариума к соседнему у Игоря уходит одна секунда. В начальный момент времени Игорь стоит около первого аквариума.

Вычислите, в течение какого наибольшего периода времени Игорь сможет добросовестно выполнять свою работу.

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

В первой строке входного файла содержится целое число \(n\) (\(2 \le n \le 50\)) - количество аквариумов с рыбками гуппи в НИИ ихтиологии. Каждая из следующих \(n\) строк содержит одно целое число \(a_i\) (\(1 \le a_i \le 2007\)) - численность \(i\)-й колонии.

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

В выходной файл выведите момент времени, когда родится первая рыбка гуппи, запись о рождении которой Игорь сделать не сможет.

Примечание

В приведенном примере Игорь сначала ждет у первого аквариума появления рыбки на 4-й секунде. После этого он бежит к третьему аквариуму (на это у него уходит 2 секунды) и как раз успевает к рождению рыбки на 6-й секунде. Однако вернуться к первому аквариуму, где следующая рыбка родится на 7-й секунде, он уже не успевает.

Примеры
Входные данные
3
996
1
994
Выходные данные
7
Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест