Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
#746
Коммерческий калькулятор
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым оказывается нарушен классический принцип “от перестановки мест слагаемых сумма не меняется”). Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в 1.05 €), потом результат с 12 (1.65 €), и затем с 13 (2.3 €), то всего мы заплатим 5 €, если же сначала отдельно сложить 10 и 11 (1.05 €), потом 12 и 13 (1.25 €) и, наконец, сложить между собой два полученных числа (2.3 €), то в итоге мы заплатим лишь 4.6 €. Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.

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

Первая строка входных данных содержит число N (2 ≤ N ≤ 105). Во второй строке заданы N натуральных чисел, каждое из которых не превосходит 10000.

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

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

Примеры
Входные данные
4
10 11 12 13
Выходные данные
4.60
Входные данные
2
1 1
Выходные данные
0.10
#752
RMQ
  
ограничение по времени на тест
1.5 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке вводится натуральное число N (1 ≤  N ≤ 105) – количество элементов в массиве. В следующей строке содержатся N целых чисел, не превосходящих по модулю 109 – элементы массива. Далее идет число K  (0 ≤ K ≤ 105) – количество запросов к структуре данных. Каждая из следующих K строк содержит два целых числа l и r (1 ≤ l ≤ r ≤ N) – левую и правую границы отрезка в массиве для данного запроса.

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

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

Примеры
Входные данные
5
7 3 1 6 4
3
1 5
2 4
3 3
Выходные данные
7 1
6 4
1 3
Входные данные
1
0
1
1 1
Выходные данные
0 1
Входные данные
2
0 1
3
1 1
1 2
2 2
Выходные данные
0 1
1 2
1 2
#753
Непересекающиеся отрезки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Их объединяют в группы по следующим правилам:
1. Несколько подряд идущих отрезков, ни один из которых не принадлежит ни одной из групп, могут быть объединены в группу.
2. Любая ранее созданная группа может быть уничтожена, при этом входившие в нее отрезки больше не относятся ни к какой группе и могут впоследствии быть отнесены к другим группам.

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

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

Первоначально нет ни одной группы.

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

Первая строка входных данных содержит число N – количество отрезков и число K – количество запросов (1 ≤ N, K ≤105). Далее идет K строчек, содержащих запросы к структуре данных. Каждый запрос начинается с числа 1 (запрос на создание группы) или 2 (запрос на удаление группы). После числа 1 указывается два других числа l и r (1 ≤ l ≤ r ≤ N), после числа 2 указывается одно число i (1 ≤ i ≤ N).

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

Для каждого запроса типа 1 необходимо отрезки с номерами от l до r объединить в группу. Если все эти отрезки не входят ни в одну группу, запрос считается удачным и программа должна вывести 1. Если хотя бы один из этих отрезков уже относится к какой-то группе, запрос считается неудачным, объединение не производится и программа выводит 0.

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

Разбалловка для личной олимпиады

Тесты 1-1 — из условия. Оцениваются в 0 баллов.

Тесты 2-11 — n, q не превосходят 1000. Каждый тест оценивается в 7 баллов.

Тесты 13-27 — дополнительных ограничений нет. Группа тестов оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы и всех тестов предыдущих групп. (вместе с предыдущими группами — 100 баллов).

Примеры
Входные данные
5 6
1 1 2
1 4 5
1 2 4
2 5
2 1
2 4
Выходные данные
1
1
0
4 5
1 2
0 0
#754
Пирамидальная сортировка
  
Темы: [Куча]
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

Отсортируйте данный массив. Используйте пирамидальную сортировку.

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

Первая строка входных данных содержит количество элементов в массиве N,  N  ≤  105. Далее задаются N целых чисел, не превосходящих по абсолютной величине 109.

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

Выведите эти числа в порядке неубывания.

#755
Хипуй!
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

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

   a) Insert(k) – добавить в Heap число k (1 ≤  k ≤ 1000000) ;
   b) Extract достать из Heap наибольшее число (удалив его при этом).

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

В первой строке содержится количество команд N (1 ≤  N ≤ 100000), далее следуют N команд, каждая в своей строке.  Команда может иметь  формат: “0 <число>” или “1”, обозначающий, соответственно, операции Insert(<число>) и Extract. Гарантируется, что при выполенении команды Extract в структуре находится по крайней мере один элемент.

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

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

Примеры
Входные данные
2
0 10000
1
Выходные данные
10000
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест