Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 74 75 76 77 78 79 80 >> Отображать по:
#604
Дополнение - 1
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
3
0 1 20
1 0 10
20 10 0
0 1 0
1 0 0
0 0 0
Выходные данные
10
#605
Связанное множество
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Даны несколько точек на плоскости, некоторые из которых соединены отрезками. Множество точек называется связанным, если из любой его точки можно перейти в любую точку, перемещаясь только по отрезкам (переходить с отрезка на отрезок возможно только в точках исходного множества). Можно за определенную плату добавлять новые отрезки (стоимость добавления равна длине добавляемого отрезка). Требуется за минимальную стоимость сделать данное множество связанным.

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

В первой строке входных данных содержится одно целое число \(N\) (1 ≤ \(N\) ≤ 50) – количество точек. Далее в \(N\) строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число \(M\) – количество уже существующих отрезков. В следующих \(M\) строках записаны по 2 числа – номера начала и конца соответствующего отрезка.

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

Вывести единственное число – минимально возможную стоимость дополнения с точностью 5 знаков после запятой.

Примеры
Входные данные
3
1 1
1 2
10 1
1
2 1
Выходные данные
9.0
#606
Дополнение - 2
  

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

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

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

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

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

Примеры
Входные данные
3
0 0 5 
0 0 0 
5 0 0
Выходные данные
0
#608
Витрина
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 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
#610
Ломаные
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На окружности отметили \(N\) точек и пронумеровали их последовательно числами от 1 до \(N\). Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами \(i\) и \(j\).

Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).

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

Вводятся три натуральных числа \(N\), \(i\), \(j\) (2 ≤ \(N\) ≤ 2 000, 1 ≤ \(i\) < \(j\) ≤ \(N\)).

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

Требуется вывести остаток от деления количества ломаных на \(10^9\).

Примеры
Входные данные
4 1 3
Выходные данные
5
Входные данные
5 1 4
Выходные данные
12
Страница: << 74 75 76 77 78 79 80 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест