Страница: << 1 2 3 4 Отображать по:

#3407

Темы: [Куча]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2007, Задача F ]

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

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

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

момент времени	размер колонии	время до очередной рыбки
0	996	4
4	997	3
7	998	2
9	999	1
10	1000	1
11	1001	1
12	1002	1
...	...	...

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

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

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

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

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

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

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

Примечание

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

Примеры

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

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

#3583

Башня

Темы: [Динамическое программирование] [Дерево отрезков, RSQ, RMQ] [Стек]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2011, Лига А, Задача G ]

Петя в очередной раз купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет A_i кубиков.

Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.

Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. В различных вариантах группировки часть столбиков могут не принадлежать ни одной из башен. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна.

Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.

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

В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 100 000). Далее на следующей строке содержатся N целых чисел, обозначающих A_i (1 ≤ A_i ≤ 10⁶).

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

На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.

Примеры

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

1 1
1

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

1
1

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

2 1
1 1000000

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

2
1 2

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

8 3
1 2 3 4 1 6 7 8

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

2
2 6

#111253

Гистограмма

Темы: [Стек]

Источники: [ Командные олимпиады, Барнаульские командные турниры, 2009, Задача F ]

Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 2, 1, 4, 5, 1, 3, 3. Все прямоугольники на этом рисунке имеют ширину, равную 1.

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

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

В первой строке входного файла записано число $N$ ($0$ < $N$ ≤ $10^6$) - количество прямоугольников гистограммы. Затем следует $N$ целых чисел $h_1 ... h_n$, где $0$ ≤ $h_i$ ≤ $10^9$. Эти числа обозначают высоты прямоугольников гистограммы слева направо. Ширина каждого прямоугольника равна $1$

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

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

Примеры

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

7 2 1 4 5 1 3 3

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

#111662

Красивые номера

Темы: [Хеш]

Источники: [ Командные олимпиады, Турнир Архимеда, 2013, Задача C ]

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

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

$\text{[math]}$

Таким образом, каждой букве соответствует некая цифра, и вместо телефонного номера достаточно знать слово, буквы которого соответствуют цифрам номера.

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

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

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

В первой строке вводится целое число N — количество новых фирм (1 ≤ N ≤ 10³).

В последующих N строках вводятся названия фирм. Название каждой фирмы состоит из семи строчных латинских букв. Гарантируется, что названия всех фирм различны.

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

Выведите одно число — максимальное количество фирм, которые смогут получить удобный номер.

Примеры

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

4
lacoste
hyundai
renault
peugeot

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

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

3
aaaaaaa
bbbbbbb
ccccccc

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

Страница: << 1 2 3 4 Отображать по:

Выбрано

Отменить

Добавить в контест