Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 20 21 22 23 24 25 26 >> Отображать по:
#3013
Точки на плоскости
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Есть квадратная клетчатая плоскость состоящая из n × n клеток (1 ≤ n ≤ 1000). Изначально в каждой клетке записано значение ноль. Ваша задача — написать программу, умеющую отвечать на следующие запросы:

  • ADD x y — увеличить значение в ячейке x, y на 1.
  • GET x1 y1 x2 y2 — вернуть сумму значений в прямоугольнике с углами в x1, y1 и x2, y2 соответственно.

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

В первой строке входного файла содержится два числа — n и k — размер доски и число запросов соответственно. Следующие k строк содержат сами запросы. Гарантируется, что общее число запросов не превосходит 300 000.

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

Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.

Примеры
Входные данные
5 15
ADD 1 1
ADD 2 2
ADD 3 3
ADD 4 4
ADD 5 5
ADD 1 5
ADD 2 4
ADD 3 3
ADD 4 2
ADD 5 1
GET 1 1 5 5
GET 2 1 5 5
GET 1 2 5 5
GET 2 2 4 4
GET 3 3 3 3
Выходные данные
10
8
8
6
2
#3204
Отрезки на прямой возвращаются
  

На прямой задано \(N\) попарно различных отрезков \([a_i, b_i]\) (\(i = 1, 2, \dots, N\), \(a_i < b_i\)). Будем говорить, что отрезок номер \(i\) непосредственно содержится в отрезке номер \(j\) (\(i \ne j\)), если:

  • он полностью принадлежит \(j\)-му (то есть \(a_j \le a_i\) и \(b_i \le b_j\)),
  • среди заданных \(N\) отрезков не найдётся такого отрезка (с номером \(k\)), что \(i\)-й отрезок принадлежит \(k\)-му и \(k\)-й принадлежит \(j\)-му (здесь \(i\), \(j\) и \(k\) - различные числа).

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

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

Сначала вводится целое число \(N\) (\(1 \le N \le 100\,000\)). Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(-10^9 \le a_i < b_i \le 10^9\)).

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

Выведите \(N\) чисел. Число номер \(i\) должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер \(i\), либо 0 - если такого не существует.

Если существует несколько решений, выведите любое.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Off-line группа, полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
Выходные данные
3 4 0 0
#3205
Отрезки на прямой возвращаются--2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Проверяющей программе доступно три блока информации:

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

Ваша задача - написать программу, которая по этим данным определит, правильно ли программа абстрактного участника посчитала ответ.

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

Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.

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

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

Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
2 2 1 0
3 4 0 0
Выходные данные
OK
WA
WA
OK
#3300
Простой максимальный поток
  
Темы: [Потоки] [Хеш]

Эта задача настолько проста, что у нее нет даже условия.

Дано N вершин неориентированного графа, M ребер, пропускная способность которых равна 1, и K запросов. Каждая вершина задается строкой, состоящей из маленьких латинских букв, длиной не более 10 символов. Для каждого запроса найдите величину максимального потока из одной вершины в другую. Вот и все.

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

В первой строке входного файла вводится 3 целых числа: N (1<=N<=5*10^5), M (0<=M<=5*10^5) и K (0<=K<=1000). Далее следует M строк, в каждой из которых через пробел записаны имена 2-ух вершин, что означает, что из одной вершины в другую есть ребро. Далее следует K запросов в том же виде, в котором задаются ребра. Запрос означает, что нужно вывести величину максимального потока из одной вершины в другую. Ответ на каждый запрос нужно выводить в отдельной строке. Гарантируется, что на вход поступает не более 2 запросов, при которых величина максимального потока положительна.

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

Выведите ответ на поставленную задачу в указанном в условии формате.

Примеры
Входные данные
7 11 1
smity grepik
dop grepik
smity rojer
rojer dop
dop jack
sanek jack
dop sanek
hello sanek
hello grepik
dop hello
rojer jack
smity sanek
Выходные данные
2
#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
Страница: << 20 21 22 23 24 25 26 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест