Темы --> Информатика --> Структуры данных --> Деревья
    Куча(30 задач)
    Двоичное дерево поиска(24 задач)
    Дерево отрезков, RSQ, RMQ(90 задач)
    Бор(14 задач)
    Дерево Фенвика(6 задач)
    Декартово дерево(10 задач)
---> 14 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 1 2 3 >> Отображать по:
#1663
Суперминимум
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N чисел. Для каждых K подряд идущих чисел найти минимальное среди них.

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

В первой строке даны числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N), разделенные пробелом. Во второй строке записано N целых чисел через пробел. Числа находятся в диапазоне от -32768 до 32767.

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

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

Пример

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

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

11 3

8 764 1 3 85 2 4 5 77 1 5

1 1 1 2 2 2 4 1 1

     

#1672
Спутник
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Требуется выполнять две операции: прибавить к ячейке X число Y и определять сумму с L по R.

Секретная корпорация, занимающаяся поиском инопланетных жизненных форм обнаружила на одной из планет созвездия Альфа удивительные живые организмы (даже не плоские, а одномерные). Она приняла решение вести наблюдение за развитием и изменением численности организмов, с этой целью на орбиту планеты был послан спутник - наблюдатель, который мог следить за изменениями численности организмов. Недостаток этого "наблюдателя" в том, что он может отслеживать изменения только на той территории планеты, которая находиться непосредственно под ним.

С этой целью его траектория была разбита на равные интервалы. Они пронумерованы от 1 до N. По запросу с Земли о количестве живых форм в интервале с L по R (L ≤ R) - спутник должен, пролетая над ними (L, L+1, …,R-1, R интервалами) произвести подсчет и затем, в ответ на запрос, отправить полученные данные. Но количество организмов постоянно изменяется: в некоторое время в X интервале на Y единиц.

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

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

Во входном файле первым записано число N (1 ≤ N ≤ 213 = 8192). Затем записана последовательность событий:

Событие

Параметры

Описание

1

X, Y

Изменение количества организмов в интервале с номером X на Y единиц.(-215 ≤ Y ≤ 215-1 = 32767)

2

L, R

Запрос суммарного количества организмов с L по R интервал.

0

  

Завершение работы.

Количество событий не превосходит 100000.

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

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

Примеры

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

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

2

1 1 4

2 1 1

2 1 1

0

4

4

4

2 1 4

1 1 3

1 4 2

2 2 4

2 1 2

1 4 -2

1 2 8

2 1 4

0

0

2

3

11
#2532
Ханты-Мансийск — Париж
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые \(c\) цифр телефонов совпадают, а \((c+1)\)-я цифра различается, то стоимость сообщения составляет \((10-c)\) кредитов (\(0\le c\le9\)). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.

Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время −2 часа от московского) своему учителю — профессору де Коде́ру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время −1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Коде́ру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.

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

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

Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Коде́ра. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число \(n_i\) (\(1\le n_i\le100\,000\)) — количество друзей Поликарпа в соответствующем городе, после которой следуют \(n_i\) строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех \(n_i\) не превосходит 100 000. Все номера телефонов во входных данных различны.

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

В первой строке выходного файла выведите минимальную возможную стоимость передачи информации \(w\) и количество задействованных в цепочке телефонных номеров \(k\). Далее выведите \(k\) номеров телефонов, описывающих саму цепочку, в порядке следования от Поликарпа к профессору де Коде́ру. Первый номер в цепочке должен совпадать с номером телефона Поликарпа, а последний — с номером телефона профессора де Коде́ра. Если решений несколько, выведите любое.

Система оценивания

  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 500, будут оцениваться из 40 баллов.
  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 5 000, будут оцениваться из 60 баллов.

    • Примеры
    Входные данные
    2099013166
7043239909
1
0258442145
1
0000000000
1
0000000001
1
0000000002
1
0147571204
    Выходные данные
    22 5
2099013166
0000000000
0000000001
0000000002
7043239909
    Входные данные
    4261802325
7967612531
1
8176476745
1
3084033164
1
1737248630
1
9447552231
1
2848478213
    Выходные данные
    40 5
4261802325
3084033164
1737248630
9447552231
7967612531
    #3871
    «Abracadabra»
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

    В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t1, t2, …, tn и набор из m строк-образцов s1, s2, …, sm. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

    Требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, …, tn, заданному числу m и m строкам-образцам s1, s2, …, sm вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

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

    Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000).

    Последующие n строк содержат слова t1, t2, …, tn, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 106. Словарь не содержит пустых слов.

    Затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000).

    Последующие m строк содержат строки-образцы s1, s2, …, sm, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 106. Никакая строка-образец не является пустой строкой.

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

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

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

    Система оценки

    Решения, работающие при \(n\), \(m\) не превосходящими 100 оцениваются из 30 баллов.

    Примеры
    Входные данные
    4
abacaba
abracadabra
aa
abra
3
a
abra
abac
    Выходные данные
    4
2
0
    #111225
    Мозаика
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    Все элементы магнитной мозаики фирмы «ABBYY» имеют прямоугольную форму. Два элемента можно соединить только в том случае, если у них совпадает хотя бы один из размеров: длина, ширина, или и то, и другое. Магнитные элементы поворачивать и переворачивать нельзя. Пару элементов мозаики, которые нельзя соединить, назовем негармоничной. Например, пара 1 × 2 и 2 × 3 является негармоничной, а пары 2 × 3 и 1 × 3 или 2 × 3 и 2 × 3 являются гармоничными. Дизайнеры «ABBYY» выложили все элементы мозаики в ряд, не соединяя их между собой. Назовем набором несколько подряд лежащих элементов мозаики в этом ряду. Они выбрали несколько наборов элементов, которые хотят оставить для создания инсталляции. Для каждого такого набора им нужно выяснить, есть ли в нем негармоничная пара элементов. Требуется написать программу, которая для различных наборов подряд лежащих элементов мозаики определит номера элементов, образующих негармоничную пару, или сообщит, что такой пары нет.

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

    В первой строке входного файла записано одно число N – количество элементов, из которых состоит мозаика (2 ≤ N ≤ 100 000). В следующих N строках записаны по два целых числа Ai и Bi , задающих длину и ширину i-го элемента мозаики соответственно (1 ≤ Ai, Bi ≤ 109, 1 ≤ i ≤ N). В (N + 2)-й строке записано одно целое число K – количество наборов, в каждом из которых нужно определить номера двух негармоничных элементов (1 ≤ K ≤ 100 000). В следующих K строках записаны пары целых чисел N1 и N2 – номера первого и последнего элементов набора соответственно, в котором необходимо найти два негармоничных элемента мозаики (1 ≤ \(N_1\) < \(N_2\) ≤ N).

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

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

    Примечание

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

    1. (оценивается в 20 баллов) Количество элементов мозаики N ≤ 100, число наборов K ≤ 100.

    2. (оценивается в 30 баллов) Количество элементов мозаики N ≤ 1000, число наборов K ≤ 1000.

    3. (оценивается в 20 баллов) Количество элементов мозаики N ≤ 5000, число наборов K ≤ 5000.

    4. (оценивается в 30 баллов) Количество элементов мозаики N ≤ 100 000, число наборов K ≤ 100 000.

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