Задача A. Ближайшее число

Автор:Известная   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Формат входного файла

Входной файл содержит целое число N за которым следует N целых чисел ai - исходная последовательность.

Формат выходного файла

В выходной файл необходимо вывести N целых чисел bi, таких что bi является ответом на задачу для числа ai.

Ограничения

1 ≤ N ≤ 106

|ai| ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
2 3 4 4
2
1
1
1

Задача B. Максимум в скользящем окне

Автор:Известная   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Формат входного файла

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел ai - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

Формат выходного файла

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 105

|ai| ≤ 109

0 ≤ m ≤ 2 n − 2

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
-3 -2 -1 0
6
RRRLLL
-2 -1 0 0 0 0
2
10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL
4 4 4 4 5 8 8 8 8 8 8 6

Problem C. Altitude and visibility

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Consider a sequence of numbers a1, …, aN, representing heights. Let's say that element ai has a visibility radius d if ai ≥ aj for all j such that 1 ≤ j ≤ N and |i − j| < d.

You task is to find maximum di for every ai.

Input file format

Input file contains integer N followed by N integers ai.

Output file format

Output file must contain N integers di — maximum visibility for every ai. If maximum visibility radius for element ai is unlimited, output di = 0.

Constraints

1 ≤ N ≤ 106, 0 ≤ ai ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
10
0 
2
6
1 5 2 2 1 4
1 0 1 2 1 4 

Задача D. Мёд и справедливость

Автор:Кленин А. С.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит ai микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M+1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

Формат входных данных

Входные данные содержат целое число N, за которым следует N чисел ai.

Формат выходных данных

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ ai ≤ 105

Примеры тестов

Стандартный вход Стандартный выход
1
3
1 1 2
1 2 3
2
2
2 5
-1

Задача E. Слон и куб

Автор:И. Блинов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Слон Пахом любит играть с кубами, и недавно приобрёл интересный куб, состоящий из M × M × M ячеек. Каждая ячейка куба содержит целое число.

На внешние ячейки куба, расположенные с трёх сторон, обозначенных на рисунке цифрами 1, 2 и 3, можно нажимать. В результате нажатия числа в ячейке, на которую нажали и во всех ячейках, находящихся за ней (то есть пересекаемых прямой, проведённой через центр нажатой ячейки перпендикулярно стороне куба), увеличиваются на 1.

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

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

Оси координат расположены, как показано на рисунке. Координаты по каждой оси отсчитываются начиная с 1 в направлении, указанном стрелкой.

Описание нажатия на ячейку состоит из номера стороны куба, на которой она расположена, и двух координат: x и y для стороны 1, y и z для стороны 2, x и z для стороны 3.

Описание запроса Вилки состоит из номера стороны куба, которой параллельна плоскость среза, и координаты: z для стороны 1, x для стороны 2, для y для стороны 3. На рисунке показан срез, параллельный стороне 1 с координатой z = 2.

Формат входного файла

Входной файл содержит целые числа M — размер куба и N — количество описаний, за которыми следует N описаний. Каждое описание начинается с целого числа Qi.

Если Qi = 1, то это описание нажатия ячейки, и далее следует целые числа ni ui vi pi — номер стороны, с которой производится нажатие, первая и вторая координаты ячейки на стороне и количество подряд идущих нажатий данной ячейки.

Если Qi = 2, то это описание запроса суммы на срезе, и далее следуют целые числа ni wi — номер стороны, которой параллельна плоскость среза, и соответствующая координата.

Формат выходного файла

Выходной файл должен содержать по одному целому числу на каждый запрос суммы.

Ограничения

1 ≤ wi, ui, vi ≤ M ≤ 103, 1 ≤ N ≤ 105, 1 ≤ pi ≤ 10, 1 ≤ Qi ≤ 2, 1 ≤ ni ≤ 3.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 2
1 1 1 1 2
2 1 1
2
2
5 4
1 1 5 5 3
2 2 5
2 1 1
2 3 1
15
3
0
3
3 11
1 1 1 1 1
1 1 1 2 1
1 1 1 3 1
1 1 2 1 3
1 1 2 2 1
1 1 2 3 1
1 1 3 1 5
1 1 3 2 1
1 1 3 3 1
2 2 2
2 3 1
15
27

Задача F. Распознавание метки

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Приложение дополненной реальности пытается найти на изображении, полученном с камеры телефона, метку, представляющую собой ярко раскрашенный прямоугольник. Благодаря контрастному цвету прямоугольника на этапе предварительной обработки изображение удалось преобразовать в массив из W на H элементов, каждый из которых равен либо '#' (ASCII 35), если он принадлежит прямоугольнику, либо '.' (ASCII 46) в противном случае.

Алгоритм предварительной обработки неидеален, и мог совершить от 0 до N ошибок — выдать '#' вместо '.' или наоборот.

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

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

Формат входного файла

Первая строка входного файла содержит целые числа W H N. Следующие H строк содержат по W символов . и # каждая — изображение после предварительной обработки.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество возможных расположений метки.

Ограничения

1 ≤ W, H ≤ 100, 0 ≤ N ≤ W × H

Описание системы оценивания

Решения работающие для W, H ≤ 20 оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 1
.#.
##.
...
3
2
2 2 0
#.
.#
0

Задача G. Сумма не без разнообразия

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Задана последовательность целых чисел A1, A2, …, AN. Необходимо выбрать из нее подпоследовательность из подряд стоящих чисел Ai, Ai+1, …, Aj так, чтобы она содержала не менее K различных чисел, и сумма S = Ai + Ai+1 + … + Aj была максимальной.

Формат входного файла

Первая строка ввода содержит целые числа N и K (1 ≤ K ≤ N ≤ 200 000). Вторая строка содержит N целых чисел A1, A2, …, AN (lvert Airvert ≤ 1 000 000 000).

Формат выходного файла

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

Ограничения

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 3
-99 1 2 -100 3 2 3
-89
2 7
2
3 2
1 1 1
IMPOSSIBLE

0.235s 0.005s 27