Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 28 29 30 31 32 33 34 >> Отображать по:
#3493
Пирамида (минимум)
  
Темы: [Куча]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Задача отличается от задачи «Пирамида (максимум)» исключительно тем, что надо извлекать не максимум, а минимум.

Напишите программу, которая будет обрабатывать последовательность запросов таких видов:

CLEAR — сделать пирамиду пустой (если в пирамиде уже были какие-то элементы, удалить все). Действие происходит только с данными в памяти, на экран ничего не выводится.

ADD n — добавить в пирамиду число n. Действие происходит только с данными в памяти, на экран ничего не выводится.

EXTRACT — вынуть из пирамиды минимальное значение. Следует и изменить данные в памяти, и вывести на экран или найденное минимальное значение, или, если пирамида была пустой, слово "CANNOT" (большими буквами).

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

Во входных данных записано произвольную последовательность запросов CLEAR, ADD и EXTRACT — каждый в отдельной строке, согласно вышеописанному формату.

Суммарное количество всех запросов не превышает 200000.

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

Для каждого запроса типа EXTRACT выведите на стандартный выход (экран) его результат (в отдельной строке).

Примечание

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

priority_queue<T> the_heap; а пирамиду с минимумом в корне — как

priority_queue<T, vector<T>, greater<T> > the_heap; При этом, второй параметр (vector<T>) задает тип контейнера, в котором будет храниться пирамида (и менять вектор на что бы ни было другое практически никогда не бывает целесообразно), а третий параметр (который, когда ничего не сказано, равен less<T>) задает, какую операцию следует использовать при проверке основного свойства пирамиды в качестве операции «меньше». Когда на место операции «меньше» подставляется операция «больше» — как раз и получается, что упорядоченность пирамиды заменяется на противоположную.

Разумеется, вместо T следует написать тип элементов, которые будем хранить в пирамиде.

Примеры
Входные данные
ADD 192168812
ADD 125
ADD 321
EXTRACT
EXTRACT
CLEAR
ADD 7
ADD 555
EXTRACT
EXTRACT
EXTRACT
Выходные данные
125
321
7
555
CANNOT
#3494
Алгоритм Дейкстры за $M$~log$N$
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до N–1 каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до N–1 — вершина, расстояния от которой надо искать.

Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.

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

Выведите на стандартный выход (экран) NUM строк, в каждой из которых по Ni чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).

Примеры
Входные данные
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1
Выходные данные
18 0 5 2 8
#3556
Бинарное дерево (вставка, поиск)
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить» и «найти» (по значению). Программа должна обрабатывать запросы трёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

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

В каждой строке входных данных записан один из запросов ADD n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

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

Для каждого запроса выводите ответ на него. Для запросов ADD и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template<class T> void print_tree(Node<T> *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i<level; i++)

    cout << ".";

  cout << p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры
Входные данные
ADD 2
ADD 3
ADD 2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7
Выходные данные
DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO
#3557
Бинарное дерево (вставка, поиск, удаление)
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить», «удалить» и «найти» (по значению). Программа должна обрабатывать запросы четырёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

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

В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

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

Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template<class T> void print_tree(Node<T> *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i<level; i++)

    cout << ".";

  cout << p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры
Входные данные
ADD 2
ADD 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 0
PRINTTREE
DELETE 7
PRINTTREE
Выходные данные
DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.0
2
..5
.7
DONE
.0
2
.5
#3558
Система непересекающихся множеств
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Напишите программу, которая будет содержать реализацию структуры данных для совокупности непересекающихся подмножеств (disjoint sets) и обрабатывать запросы таких видов:

RESET n — создать новую серию подмножеств: множество из одного только элемента 0, из одного только элемента 1, и так до множества из одного только элемента n–1 включительно. Если структура уже содержала какую-то другую совокупность непересекающихся подмножеств, вся соответствующая информация утрачивается. На стандартный выход (экран) при этом следует вывести два слова через пробел «RESET DONE».

JOIN j k — объединить подмножества, которым принадлежат элемент j и элемент k. Если элементы и так принадлежали одному подмножеству, вывести на стандартный выход (экран) слово «ALREADY», после него через пробелы те же числа j и k в том же порядке. Если элементы до сих пор принадлежали разным подмножествам, то действие происходит только с данными в памяти, на экран ничего не выводится.

CHECK j k — проверить, одному ли подмножеству принадлежат элемент j и элемент k; вывести на стандартный выход (экран) слово «YES» (если одному) или слово «NO» (если разным).

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

Во входных данных содержится последовательность запросов RESET, JOIN и CHECK — каждый в отдельной строке, согласно вышеописанному формату. Гарантированно, что первая строка содержит запрос RESET, а общее количество запросов RESET не превышает 5. Общее количество всех запросов не превышает 200000. Значение n в каждом запросе RESET не превышает 100000. В каждом запросе JOIN и в каждом запросе CHECK оба числа будут в диапазоне от 0 до n–1, где n — параметр последнего выполненного запроса RESET.

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

Для запросов RESET, CHECK и тех запросов JOIN, где элементы и так принадлежат одному подмножеству, выводить на стандартный выход (экран) соответствующий результат (в отдельной строке).

Примечание

Ответы «NO» даются на запросы «CHECK 2 11» и «CHECK 9 1», ответ «ALREADY 4 1» — на второй из запросов «JOIN 4 1» (10-я строка), «YES» — на «CHECK 5 10».

Примеры
Входные данные
RESET 15
JOIN 14 10
JOIN 13 8
JOIN 0 9
JOIN 8 3
JOIN 4 1
JOIN 10 5
JOIN 8 4
CHECK 2 11
JOIN 4 1
JOIN 2 6
CHECK 9 1
JOIN 6 5
CHECK 10 5
Выходные данные
RESET DONE
NO
ALREADY 4 1
NO
YES
Страница: << 28 29 30 31 32 33 34 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест