| | | |
|
Сумма, делящаяся на заданное число
Линейные структуры
Необходимо найти самый большой непрерывный фрагмент в
последовательности a1,a2...aN, сумма элементов которого делится на P.
Входные данные
В первой строке содержатся натуральные числа P, N (2≤P≤100, 1≤N≤100000).
В следующих N строках содержатся элементы последовательности - по одному числу в строке.
Все числа по модулю не превосходят 109 .
Выходные данные
Выведите два числа — индексы начала и конца фрагмента.
Если таких фрагментов несколько, то выведите фрагмент
с минимальным индексом начала.
Если ответа не существует, то выведите единственное число −1.
Примеры:
| входные данные |
выходные данные |
3 4
1
2
3
4 |
1 3 |
3 2
1
1 |
-1 |
| |
![]()
|
|
Одномерные массивы. Введение
Линейные структуры
В программе измените объявление массива таким образом, чтобы массив состоял из 30 элементов.
| |
![]()
|
|
Двумерный дождь
Префиксные суммы(минимумы, ...)
Линейные структуры
Игра 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 |
Замечание
Пример соответствует рисунку. Черным цветом обозначен камень, серым вода.
| |
![]()
|
|
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, поэтому необходимо как минимум два раунда.
| |
![]()
|
