Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 15 16 17 18 19 20 21 >> Отображать по:
#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
#1738
Сортировка вагонов
  
Темы: [Стек]

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

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

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

Вводится число \(N\) — количество вагонов в поезде (1≤N≤2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до \(N\), каждое из которых встречается ровно один раз.

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

Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:

1) если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число \(K\) (\(K\)≥1),

2) если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число \(K\) (\(K\)≥1).

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

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

Примеры
Входные данные
3
3 2 1
Выходные данные
YES
Входные данные
4
4 1 3 2
Выходные данные
YES
Входные данные
3
2 3 1
Выходные данные
NO
#1745
Ездящий город
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мосгортранс в честь дня своего рождения решил провести соревнования, и, по аналогии с «Бегущим городом» назвать их «Ездящий город».

Участник соревнований получает маршрутный лист, где указано, какие контрольные пункты и в каком порядке он должен посетить (в каждом пункте участник должен отметиться). При этом участник должен отмечаться в пунктах строго в указанном порядке. Какие-то пункты может потребоваться посетить несколько раз.

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

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

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

Сначала вводится число \(N\) — общее количество контрольных пунктов (2≤\(N\)≤10000).

Далее вводится количество автобусных маршрутов \(K\) (1≤\(K\)≤50000). Далее идет \(K\) описаний автобусных маршрутов.

Каждый маршрут описывается четырьмя числами \(A_i\), \(B_i\), \(C_i\), \(D_i\), которые означают, что каждые \(C_i\) минут (т.е. в моменты времени 0, \(C_i\), 2*\(C_i\), …) автобус выходит от контрольного пункта \(A_i\) и через \(D_i\) минут прибывает к контрольному пункту \(B_i\). Все \(C_i\) и \(D_i\) — натуральные и не превышают 10000.

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

Далее вводится число \(M\) — количество контрольных пунктов в маршрутном листе участника (2≤\(M\)≤50). Далее вводятся \(M\) чисел \(P_1\), \(P_2\), …, \(P_M\) — номера контрольных пунктов, которые нужно посетить (числа в этом списке могут повторяться). В момент времени 0 участник находится в пункте \(P_1\). Временем прохождения маршрута считается момент времени, когда участник окажется в пункте \(P_M\).

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

Выведите одно число — минимальное время, за которое участник может пройти маршрут. Если существующие автобусные рейсы не позволяют пройти маршрут, выведите одно число –1 (минус один).

Примеры
Входные данные
2 2
2 1 3 1
1 2 5 4
3
1 2 1
Выходные данные
7
Входные данные
3 4
2 1 30 10
1 2 50 40
2 3 45 10
3 1 55 10
3
1 2 1
Выходные данные
65
Входные данные
2 2
1 2 3 1
1 2 5 4
3
1 2 1
Выходные данные
-1
#1750
Подпалиндромы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.

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

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

Вводится одна строка, состоящая из маленьких латинских букв. Длина строки не превышает 100000 символов.

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

Выведите одно число — количество подстрок данной строки, являющихся палиндромами

Примеры
Входные данные
aaa
Выходные данные
6
Входные данные
aba
Выходные данные
4
#1754
Конкатенация
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дано множество строк W. Необходимо найти минимальное множество строк X, такое, что путем конкатенации строк мн-ва X можно составить то же мн-во, что и путем конкатенации строк W

Рассмотрим две строки \(α\) и \(β\). Их конкатенацией называется строка, получающаяся в результате приписывания к строке \(α\) строки \(β\). Эта строка обозначается \(αβ\). Например, конкатенацией строк `ab' и `ac' будет строка `abac'. Очевидно, что это определение естественным образом распространяется на конкатенацию произвольного количества строк. Так, конкатенацией нуля строк будет пустая строка, а конкатенацией одной строки будет она сама.

Рассмотрим некоторое множество \(W\), состоящее из строк. Назовём его замыканием множество \(W\)*, состоящее из тех и только тех строк, которые можно получить в результате конкатенации нуля и более строк из множества \(W\). Таким образом, множество \(W\)* содержит пустую строку, и если строка α принадлежит множеству \(W\)*, а строка \(β\) принадлежит множеству \(W\), то строка \(αβ\) принадлежит множеству \(W\)*. Более того, все элементы множества \(W\)* можно представить в таком виде, то есть \(W\)* является пересечением всех множеств с указанными выше свойствами. Например, если \(W\)={a,ab}, то \(W\)* состоит из всех строк, в которых перед каждой буквой `b' идёт хотя бы одна буква `a'.

Задано некоторое множество строк \(W\). Требуется найти множество \(X\), такое, что \(W\)*=\(X\)* и множество \(X\) имеет минимальное возможное число элементов. В случае, если таких множеств несколько, подходит любое из них. Например, если \(W\)={a,aabb,ab,ac,b,bac}, то единственным множеством, удовлетворяющим условиям задачи будет множество {a,ac,b}.

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

Входной файл состоит из набора строк, каждая из которых является элементом множества \(W\). Каждая строка из множества \(W\) встречается во входном файле хотя бы один раз. Суммарная длина всех строк во входном файле не превосходит \(10^4\). Количество строк во входном файле не превосходит \(10^4\). После каждой строки из множества \(W\) во входном файле идёт перевод строки (пара символов с ASCII кодами 13 и 10). Строки состоят из символов с ASCII кодами от 33 до 126 включительно.

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

Выведите в выходной файл элементы одного из множеств \(X\), удовлетворяющих условиям задачи. Каждая строка множества \(X\) должна быть выведена ровно один раз. Строки должны идти в лексикографическом порядке (лексикографический порядок используется в словарях, в этом порядке строка `ab' меньше строки `aba' и строка `ab' меньше строки `ac'). После каждой строки множества \(X\) должен идти один перевод строки.

Примеры
Входные данные
a
aabb
ab
ac
b
bac
Выходные данные
a
ac
b
Страница: << 15 16 17 18 19 20 21 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест