Алгоритм Дейкстры(33 задач)
    Алгоритм Флойда(20 задач)
    Обход в ширину(61 задач)
    Алгоритм Форда-Беллмана(6 задач)
---> 115 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите 0, если в заданном графе цикла нет, и 1, если он есть.

Примеры
Входные данные
3
0 1 0
0 0 1
0 0 0
Выходные данные
0
Входные данные
3
0 1 0
0 0 1
1 0 0
Выходные данные
1
Максимальное время работы на одном тесте:   5 секунд

В неориентированном графе требуется найти минимальный путь между двумя вершинами.

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

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

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

Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.

Необходимо вывести путь (номера всех вершин в правильном порядке). Если пути нет, нужно вывести -1.

Примеры
Входные данные
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
Выходные данные
3
3 2 1 5
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Максимальное время работы на одном тесте: 1 секунда

На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

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

На вход программы поступает  пять чисел: N, x1, y1, x2, y2 (5 <= N <= 20, 1 <= x1, y1, x2, y2 <= N). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).

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

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

Пример выходного файла ниже неполный, правильный пример такой:

4
3 3
2 1
1 3
3 2
5 1
Примеры
Входные данные
5
3 3
5 1
Выходные данные
4
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Максимальное время работы на одном тесте: 1 секунда

Дана таблица, состоящая из N строк и M столбцов. В каждой клетке таблицы записано одно из чисел: 0 или 1. Расстоянием между клетками (x1, y1) и (x2, y2) назовем сумму |x1-x2|+|y1-y2|. Вам необходимо построить таблицу, в клетке (i, j) которой будет записано минимальное расстояние между клеткой (i, j) начальной таблицы и клеткой, в которой записана 1. Гарантируется, что хотя бы одна 1 в таблице есть.

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

В первой строке вводятся два натуральных числа N и M, не превосходящих 500. Далее идут N строк по M чисел - элементы таблицы.

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

Требуется вывести N строк по M чисел - элементы искомой таблицы.

Примеры
Входные данные
2 3
0 0 1
1 0 0
Выходные данные
1 1 0 
0 1 1 
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Максимальное время работы на одном тесте: 1 секунда

На стандартной шахматной доске (8х8) живут 2 шахматных коня: Красный и Зеленый. Обычно они беззаботно скачут по просторам доски, пощипывая шахматную травку, но сегодня особенный день: у Зеленого коня День Рождения. Зеленый конь решил отпраздновать это событие вместе с Красным. Но для осуществления этого прекрасного плана им нужно оказаться на одной клетке. Заметим, что Красный и Зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди, а одновременно, и если оказываются на одной клетке, никто никого не съедает. Сколько ходов им потребуется, чтобы насладиться праздником?

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

На вход программы поступают координаты коней, записанные по стандартным шахматным правилам (т.е. двумя символами - маленькая латинская буква (от a до h) и цифра (от 1 до 8), задающие столбец и строку соответственно).

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

Требуется вывести наименьшее необходимое количество ходов, либо число -1, если кони не могут встретиться.

Примеры
Входные данные
a1 a3
Выходные данные
1

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