Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 234 235 236 237 238 239 240 >> Отображать по:
#3488
5D: лексикографический порядок
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Сгенерировать все ПСП длины N.

Выведите все правильные скобочные последовательности заданной длины в лексикографическом порядке.

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

Во входном файле записана натуральное число \(n\), не превосходящее 10.

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

Выведите все правильные скобочные последовательности длины \(2n\) в лексикографическом порядке, по одной последовательности в строке.

Примеры
Входные данные
3
Выходные данные
((()))
(()())
(())()
()(())
()()()
#3489
Поиск в ширину--1
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Напишите программу, которая будет реализовывать поиск в ширину в ориентированном невзвешенном не-мульти графе без петель. Вершины графа являются целыми неотрицательными числами в диапазоне от 0 до N–1 (где N — количество вершин в графе). Граф обязательно представлять списками смежности, а именно — как vector<int>[].

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

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

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

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

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

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

Примеры
Входные данные
2
3 2
0 1
1 2
1
4 4
0 1
0 3
1 2
2 3
0
Выходные данные
987654321 0 1 
0 1 2 1
#3491
Поиск в ширину--2 (вершины идентифицируются названиями)
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

Примечание

Задачу можно решить, пользуясь map<string,int> и vector<string> для преобразований имен в номера и номеров в имена; тогда внутри программы можно использовать представление графа как vector<vector<int> >. Для вывода в отсортированном порядке использовать прохождение по всем элементам от begin() до end() структуры map<string,int> (превращающей названия в номера).

Другой способ — вообще отказаться от нумерации вершин числами и представлять граф как map<string,vector<string> >; в этом случае массивы, используемые самим поиском, следует заменить на map<string,int>.

Примеры
Входные данные
2
2
Cherk Zol
Cherk Sm
Zol
4
A Bb
Bb Ccc
Ccc A
Dddd Eeeee
Bb
Выходные данные
Cherk 1
Sm 2
Zol 0
===
A 1
Bb 0
Ccc 1
#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
#3545
Замечательные числа - 2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Квадрат трехзначного числа оканчивается тремя цифрами, равными этому числу. Найдите и выведите все такие числа.

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

Программа не требует ввода данных с клавиатуры, просто выводит список искомых чисел.

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

Выведите ответ на задачу.

Страница: << 234 235 236 237 238 239 240 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест