Линейные структуры


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 25971. Одномерные массивы. Введение
Темы: Линейные структуры   

В программе измените объявление массива таким образом, чтобы массив состоял из 30 элементов.
ID 27041. Двумерный дождь
Темы: Префиксные суммы(минимумы, ...)    Линейные структуры   

Игра PitCraft происходит в двумерном мире, который состоит из блоков размером 1 на 1 метр.
Остров игрока представляет собой набор столбцов различной высоты, состоящих из блоков камня и окруженный морем.
Над островом прошёл сильный дождь, который заполнил водой все низины, а не поместившаяся в них вода стекла в море, не увеличив его уровень. По ландшафту острова определите, сколько блоков воды осталось после дождя в низинах на острове.
 
Формат входных данных
В первой строке записано натуральное число N (0 <= N <= 100 000)  количество столбцов, задающих ландшафт острова.
Во второй строке записано N натуральных чисел Hi (1 <= Hi <= 109)  высоты столбцов.
 
Формат выходных данных
Выведите одно число  количество блоков занятых водой.
Система оценки
Решения, верно работающие при N <= 100, будут набирать не менее половины баллов.
 
Ввод Вывод
11
2 5 2 3 6 9 3 1 3 4 6		 18
 
Замечание
Пример соответствует рисунку. Черным цветом обозначен камень, серым  вода.
ID 27219. Modern Art 2
Темы: Стек    Конструктив    Линейные структуры   

Picowso решила переключиться на 1-мерный стиль.
Теперь её картины могут описываться 1-мерным массивом цветов длины NN (1≤N≤100,000). А вот стиль у неё остался прежний: Он начинает на пустом отрезке и рисует отрезками. Она использует каждый из цветов 1…N ровно один раз, хотя некоторые из цветов могут быть полностью скрыты к концу рисования.
 
Moonet, соперник Picowso, придумал, как копировать картины Picowso. Он рисует множество не соединяющихся интервалов и т.д. Moonet может рисовать не более одного интервала каждого цвета во время всего процесса. Вычислите количество таких раундов, которые требуются Moonet, чтобы скопировать 1-мерную картину Picowso.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N, и следующие N строк содержат целое число в интервале 0…N, указывающее цвет каждой ячейки на 1-мерном холсте (0 для пустой ячейки).

ФОРМАТ ВЫВОДА:
 
Выведите минимальное количество раундов, которое требуется для копирования заданного рисунка или -1, если невозможно повторить этот рисунок стилем, аутеничным стилю Picowso (то есть, её нельзя нарисовать слоями последовательностей интервалов, по одному каждого цвета).
 
Ввод Вывод
7
0
1
4
5
1
3
3
 2

Примечание
В данном примере интервал цвета 1 должен быть закрашен в более раннем раунде, чем интервалы цветов 4 и 5, поэтому необходимо как минимум два раунда.