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

Автор:Известная   Ограничение времени: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 B. 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 

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

Автор:Известная   Ограничение времени: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

Задача D. 2048(failed)

Автор:М. Спорышев   Ограничение времени:5 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб

Условие

2048!

Данная задача является интерактивной.

Задача состоит в прохождении игры 2048 с наилучшим результатом.

2048 играется на поле N × M клеток. Клетки, в которых записаны числа, сдвигаются по нажатию пользователем клавиш курсора.

После каждого хода в случайном пустом поле появляется число 2, либо 4. Клетки сдвигаются в заданном пользователем направлении, пока их не остановит либо другая непустая клетка, либо граница поля.

Если две клетки с одинаковыми числами сталкиваются друг с другом во время сдвига, они объединяются в одну клетку с числом равным их сумме.

Клетка не может быть объединена с другими более одного раза во время сдвига. Клетки сдвигаются и объединяются последовательно от первого к последнему в направлении движения.

Протокол взаимодействия

На каждом шаге взаимодействия ваша программа должна:

  1. Считать текущее состояние игрового поля
  2. В выходной поток вывести код команды сдвига (влево, вправо, вверх, вниз)

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

Первая строка входного потока состоит из двух чисел N и M  — размеры поля.

Далее следует N строк по M чисел, задающих каждую клетку. 0  — если клетка пустая.

Входной поток содержит единственное число  — 1, если игра окончена.

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

В выходной поток необходимо вывести единственный символ, характеризующий направление сдвига.

Символ 'l'  — движение плиток влево, 'r'  — вправо, 'u'  — вверх, 'd'  — вниз.

Ограничения

Количество шагов не превышает 106

2 ≤ N, M ≤ 10


0.104s 0.006s 17