Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 321 322 323 324 325 326 327 >> Отображать по:
#3302
Type Printer
  
Темы: [Бор]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

Вам нужно напечатать \(N\) слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:

  • Добавить букву в конец слова, находящегося сейчас на принтере.
  • Удалить последнюю букву из слова, находящегося сейчас на принтере. Эту операцию можно делать, только если слово содержит хотя бы одну букву.
  • Напечатать слово, находящееся на принтере (при этом слово никуда не исчезает, можно печатать его ещё раз и ещё раз).

Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.

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

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

Ваша программа должна считать следующие входные данные:

  • На первой строке число \(N\) (\(1 \le N \le 25\,000\)).
  • На следующих \(N\) строках слова, состоящие из маленьких букв латинского алфавита. Длина каждого слова не превышает 20. Все слова различны.
Выходные данные

Ваша программа должна вывести следующие данные:

  • На первой строке \(M\) — число операций.
  • На следующих \(M\) строках по одному символу — описание операций. Каждая операция описывается одним символом:
    • Добавление символа обозначается собственно символом.
    • Удаление символа обозначается символом «-» (минус, ASCII-код 45).
    • Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).
Примеры
Входные данные
3
print
the
poem
Выходные данные
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P
#3308
Суммы на подотрезках
  
ограничение по времени на тест
10.0 second;
ограничение по памяти на тест
64 megabytes

Реализуйте структуру данных для эффективного вычисления сумм подряд идущих элементов массива.

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

В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление суммы.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).'

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

Для каждого запроса выведите сумму чисел соответствующего участка массива. Числа выводите в одну строку через пробел.

Примеры
Входные данные
5
4 4 8 7 8
2
1 2
1 3
Выходные данные
8 16
#3309
Максимумы на подотрезках
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes

Реализуйте структуру данных для эффективного вычисления максимумов подряд идущих элементов массива.

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

В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление максимума.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

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

Для каждого запроса выведите значение максимального элемента на указанном отрезке массива. Числа выводите в одну строку через пробел.

Примеры
Входные данные
5
2 2 2 1 5
2
2 3
2 5
Выходные данные
2 5
#3310
Индекс максимума на подотрезках
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes

Реализуйте структуру данных для эффективного вычисления номера максимального из нескольких подряд идущих элементов массива.

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

В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление максимума.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

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

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

Числа выводите в одну строку через пробел.

Примеры
Входные данные
5
2 2 2 1 5
2
2 3
2 5
Выходные данные
2 5
#3311
Левый максимум на подотрезке
  
ограничение по времени на тест
10.0 second;
ограничение по памяти на тест
256 megabytes

Реализуйте структуру данных для эффективного вычисления номера левого максимального из нескольких подряд идущих элементов массива.

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

В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление максимума.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

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

Для каждого запроса выведите индекс максимального элемента на указанном отрезке массива. Если максимальных элементов несколько, выведите номер самого левого их них.

Числа выводите в одну строку через пробел.

Примеры
Входные данные
5
2 2 2 1 5
2
2 3
2 5
Выходные данные
2 5
Страница: << 321 322 323 324 325 326 327 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест