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

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

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

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

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

В первой строке вводится число $n$ - количество дырок (2 <= $n$ <= 1000). Следующие n строк содержат по два целых числа - координаты дырок. Координаты не превышают $10^4$ по абсолютной величине.

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

В первой строке выведите $k$ - количество различных расстояний, которые Дима мог установить между иглами измерителя. Следующие k строк должны содержать искомые расстояния, по одному вещественному числу в строке. Расстояния должны быть выведены в возрастающем порядке. Каждое число должно быть выведено с точностью не менее, чем 10-9.

Гарантируется, что существует по крайней мере одно расстояние, которое Дима мог установить между иглами измерителя.

Примеры
Входные данные
4
0 0
1 1
1 0
0 1
Выходные данные
2
1.0
1.4142135623730951
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Зал супермаркета имеет форму прямоугольника размером $M$ x $N$, в котором расставлены витрины размером 1 x 1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.

В супермаркет привезли новую супервитрину размером $K$ x 1 и выгрузили в одном из углов супермаркета. Требуется передвинуть ее в противоположный угол супермаркета. При этом ее нельзя поворачивать, а можно лишь передвигать параллельно стенам супермаркета. Напишите программу, которая по плану супермаркета поможет определить, какое наименьшее количество витрин нужно убрать, чтобы передвинуть супервитрину.

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

В первой строке вводятся три натуральных числа $M$, $N$ и $K$ ($M$, $N$ ≤ 100, $K$ ≤ $M$). Начальное и конечное расположение супервитрины такие, как указано на верхнем рисунке. В следующей строке записано целое неотрицательно число $V$ – количество витрин (0 ≤ $V$ ≤ $N$*$M$). В следующих $V$ строках входных данных содержатся различные пары целых неотрицательных чисел, характеризующие положения витрин. Первое число (от 0 до $M$–1) – расстояние от левой стены супермаркета до витрины, второе (от 0 до $N$–1) – расстояние от нижней стены до витрины (см. нижний рисунок). Гарантируется, что там, где изначально поставили супервитрину, других витрин нет.

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

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

U – на 1 вверх,
D – на 1 вниз,
L – на 1 влево,
R – на 1 вправо.
Количество символов в строке не должно превышать $N$ x $M$.

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

Примеры
Входные данные
10 10 5
0
Выходные данные
0
RUURUURUURUURU
Входные данные
9 3 2
4
2 0
5 1
5 2
8 2
Выходные данные
1
URRRDRRRRUU
#645
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке находится число $N$, в следующих $N$ строках - по $N$ символов. Символом точки обозначена свободная клетка, латинской заглавной $O$ - шарик, $@$ - исходное положение шарика, который должен двигаться, латинской заглавной $X$ - конечное положение шарика. 2 <= $N$ <= 40.

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

В первой строке выводится $Y$, если движение возможно, или $N$, если нет. Если движение возможно, далее следует $N$ строк по $N$ символов - как и на вводе, но буква $X$, а также все точки по пути заменяются плюсами.

Примеры
Входные данные
2
@.
.X
Выходные данные
Y
@+
.+
Входные данные
2
@O
OX
Выходные данные
N
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке находится число $N$, затем идут $N$ строк по $N$ символов: точка обозначает пустой сегмент, решётка - сегмент со стеной. 3 <= $N$ <= 33, размер сегмента 3 x 3 м, высота стен 3 м.

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

Вывести одно число - площадь видимой части внутренних стен лабиринта в квадратных метрах.

Примеры
Входные данные
4
....
....
....
....
Выходные данные
108
Входные данные
4
....
.##.
.##.
....
Выходные данные
180
#651
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке находится число $N$, в следующих $N$ строках - по $N$ символов. Символом точки обозначена свободная клетка, латинской заглавной $O$ - шарик, $@$ - исходное положение шарика, который должен двигаться, латинской заглавной $X$ - конечное положение шарика. 2 <= $N$ <= 250.

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

В первой строке выводится $Y$, если движение возможно, или $N$, если нет. Если движение возможно, далее следует $N$ строк по $N$ символов - как и на вводе, но $X$, а также все точки по пути заменяются плюсами +.

Примеры
Входные данные
2
@.
.X
Выходные данные
Y
@.
++
Входные данные
2
@O
OX
Выходные данные
N

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