Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 22 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 1 2 3 4 5 >> Отображать по:
#1666
Супермногоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано N (1 ≤ N ≤ 30) супермногоугольников (без пересечений и самопересечений). Каждый супермногоугольник задаётся координатами своих Ki (3 ≤ Ki ≤ 30, 1 ≤ i ≤ N) вершин в порядке обхода против часовой стрелки. Все координаты — целые числа из диапазона -32000..32000. Требуется соединить супермногоугольники М отрезками так, чтобы:

  1. Oтрезок соединяет только пару супермногоугольников.

  2. Суммарная длина отрезков была минимальна.

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

Формат входных данных

В первой строке число N. В следующих N строках. Число Ki и Ki пар чисел – координаты вершин.

Формат выходных данных

В первой строке число М и сумма длин найденных отрезков с точностью 10-3. В следующих М строках числа L1 X1 Y1 L2 X2 Y2 – номера супермногоугольников и координаты концов отрезков с точностью 10-3.

Примеры

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

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

2

3 1 0 2 0 1 1

4 6 5 7 5 7 6 6 6

1 6.364

1 1.500 0.500 2 6.000 5.000

3

3 0 0 1 0 0 1

4 5 5 6 5 6 6 5 6

3 0 5 1 6 0 6

2 8.000

3 1.000 6.000 2 5.000 6.000

1 0.000 1.000 3 0.000 5.000
#1668
Блохи
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Блохи сидят на клетках шахматного поля и ходят конем. Должны собраться в одной из клеток. Определить сумму длин кратчайших путей.

На клеточном поле, размером \(N\)x\(M\) (2 ≤ \(N\), \(M\) ≤ 250) сидит \(Q\) (0 ≤ \(Q\) ≤ 10000) блох в различных клетках. "Прием пищи" блохами возможен только в кормушке - одна из клеток поля, заранее известная. Блохи перемещаются по полю странным образом, а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться блохам у кормушки невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.

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

В первой строке входного файла находится 5 чисел, разделенных пробелом: \(N\), \(M\), \(S\), \(T\), \(Q\). \(N\), \(M\) - размеры доски (отсчет начинается с 1); \(S\), \(T\) - координаты клетки - кормушки (номер строки и столбца соответственно), \(Q\) - количество блох на доске. И далее \(Q\) строк по два числа - координаты каждой блохи.

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

Содержит одно число - минимальное значение суммы длин путей или -1, если сбор невозможен.

Примеры
Входные данные
2 2 1 1 1
2 2
Выходные данные
-1
#1928
Производство деталей
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из \(n\) деталей, пронумерованных от 1 до \(n\), при этом деталь с номером \(i\) изготавливается за \(p_i\) секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.

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

Первая строка входного файла содержит число \(n\) (\(1\le n\le100000\)) — количество деталей двигателя. Вторая строка содержит \(n\) натуральных чисел \(p_1,p_2, \ldots,p_n\), определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит \(10^9\) секунд.

Каждая из последующих \(n\) строк входного файла описывает характеристики производства деталей. Здесь \(i\)-я строка содержит число деталей \(k_i\), которые требуются для производства детали с номером \(i\), а также их номера. В \(i\)-й строке нет повторяющихся номеров деталей. Сумма всех чисел \(k_i\) не превосходит 200000.

Известно, что не существует циклических зависимостей в производстве деталей.

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

В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число \(k\) деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел \(k\) чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Примеры
Входные данные
3
100 200 300
1 2
0
2 2 1
Выходные данные
300 2
2 1
Входные данные
2
2 3
1 2
0
Выходные данные
5 2
2 1
Входные данные
4
2 3 4 5
2 3 2
1 3
0
2 1 3
Выходные данные
9 3
3 2 1
#3184
Космические исследования
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Отделу космических исследований поступило задание сфотографировать из космоса \(n\) объектов в заданной области. Область имеет форму квадрата размером \(50\times 50\) километров. Если разделить ее на квадраты размером \(1\times 1\) километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов.

Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже.

Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером \(k\times k\) километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами \(x\) и \(y\) от \(1\) до \(k\) километров.

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

Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области.

Требуется написать программу, которая по заданному расположению объектов и размеру снимка \(k\) определит минимальное время, за которое можно сделать снимки всех объектов заданной области.

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

Первая строка входного файла содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 1000\), \(1 \le k \le 5\)).

Следующие \(n\) строк содержат по два целых числа: \(x_i\) и \(y_i\) — координаты объектов в заданной области (\(1 \le x_i, y_i \le 50\)).

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

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

Примечание

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

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

В третьем примере перемещать участок съемки не требуется, можно просто сделать снимок.

Четвертый пример соответствует приведенному выше рисунку.

Правильные решения для тестов, в которых \(k = 1\), будут оцениваться в 30 баллов.

Правильные решения для тестов, в которых \(k \gt 1\) и \(1 \lt n \le 15\), будут оцениваться так же в 30 баллов.

Примеры
Входные данные
4 1
1 1
10 2
1 3
10 4
Выходные данные
30
Входные данные
4 2
1 1
10 2
1 3
10 4
Выходные данные
10
Входные данные
1 1
1 1
Выходные данные
0
Входные данные
3 3
3 3
3 6
6 3
Выходные данные
7
#111222
Вирусы и антивирусы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Антивирусная IT-компания имеет официальную иерархическую структуру управления. В ней есть босс – единственный сотрудник, над которым нет начальника. Каждый из остальных сотрудников подчинён ровно одному сотруднику – своему начальнику. Начальник может иметь нескольких подчинённых и отдавать или передавать приказы любому из них. Приказы могут передаваться от одного сотрудника другому только по цепочке, каждый раз от начальника к его подчинённому. Сотрудник А главнее сотрудника Б в этой иерархии, если А может отдать или передать приказ сотруднику Б непосредственно, или через цепочку подчинённых. Босс главнее любого сотрудника. Оказалось, что все сотрудники объединены ещё в одну организованную подобным образом тайную иерархическую структуру, производящую компьютерные вирусы. В тайной структуре может быть другой босс, а у сотрудников – другие начальники. Будем называть пару сотрудников А и Б устойчивой, если А главнее Б и в основной, и в тайной иерархических структурах. Требуется написать программу, определяющую количество устойчивых пар в компании.

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

В первой строке задано число N – количество сотрудников компании (1 ≤ N ≤ 100 000). Во второй строке – N целых чисел ai, где ai = 0, если в официальной иерархии сотрудник с номером i является боссом, в противном случае ai равно номеру непосредственного начальника сотрудника номер i. В третьей строке – N целых чисел bi, где bi = 0, если в тайной иерархии сотрудник с номером i является боссом, в противном случае bi равно номеру непосредственного начальника сотрудника номер i. Нумерация сотрудников ведется с единицы в том порядке, в каком они упомянуты во входном файле.

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

Выходной файл должен содержать единственное число – количество устойчивых пар.

Примечание

Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

  1. (оценивается в 25 баллов) Количество сотрудников N не превосходит 100.

  2. (оценивается в 25 баллов) Количество сотрудников N не превосходит 2000.

  3. (оценивается в 50 баллов) Количество сотрудников N не превосходит 105.

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