Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Кратчайшие пути в графе
    Алгоритм Дейкстры(33 задач)
    Алгоритм Флойда(20 задач)
    Обход в ширину(62 задач)
    Алгоритм Форда-Беллмана(6 задач)
---> 29 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 2 3 4 5 6 >> Отображать по:
#14
Сталкер
  
Темы: [0-1 BFS]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

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

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

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

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

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

В первой строке входных данных содержатся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) — количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад — в здании с номером N.

В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число ri — количество дорог, обозначенных на i-ой карте. Затем идут ri строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r1 + r2 + … + rK ≤ 300 000).

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

Выведите одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число –1.

Примеры
Входные данные
12 4
4
1 6
2 4
7 9
10 12
3
1 4
7 11
3 6
3
2 5
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12
Выходные данные
3
#15
Файловый менеджер
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя работает над очень большим проектом. Проект содержит N файлов. В процессе работы Пете часто приходится просматривать и редактировать файлы. Для ускорения работы Петя использует файловый менеджер Fur Manager, который отображает список имен файлов проекта в некотором порядке.

В текущей версии Fur Manager’a для перемещения по списку имен файлов есть следующие возможности:

  1. можно нажать клавишу вниз, при этом курсор перемещается на следующий файл в списке, для последнего файла следующим считается первый;

  2. можно нажать клавишу вверх, при этом курсор перемещается на предыдущий файл в списке, для первого файла предыдущим считается последний;

  3. можно нажать клавишу Alt и, удерживая ее, набрать последовательность латинских букв. После этого клавишу Alt следует отпустить, и в этот момент курсор переместится на ближайший файл, имя которого начинается c заданной последовательности символов. Ближайший файл — это файл, на который можно переместиться за наименьшее количество нажатий клавиши вниз. Если заданная последовательность является началом имени текущего файла, или файла, имя которого начинается с этой последовательности, не существует, то курсор останется на месте.

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

Файлы пронумерованы от 1 до N в порядке их следования. После загрузки Fur Manager’а курсор находится на первом файле.

Петя знает, что ему сначала придется редактировать файл с номером a1, затем с номером a2 и так далее, а последним — файл с номером ak. В последовательности a1, a2, ..., ak один и тот же номер может встречаться несколько раз. При каждом перемещении от одного файла к другому Петя хочет нажимать как можно меньше клавиш.

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

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

В первой строке входных данных содержится целое число N (1 ≤ N ≤ 1000) — количество файлов в проекте.

В следующих N строках записаны имена файлов, по одному в каждой строке. Файлы перечислены в том порядке, в котором они отображаются файловым менеджером. Имена состоят только из строчных латинских букв. Длина каждого имени не превосходит 2000 символов. Все имена файлов различны.

Далее в следующей строке записано целое число k (1 ≤ k ≤ 10).

Последняя строка входных данных содержит k целых чисел a1, a2, ..., ak (1 ≤ ai ≤ N) — номера редактируемых файлов. Редактирование файлов выполняется в том порядке, в котором они встречаются в последовательности a1, a2, ..., ak.

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

Выведите описание искомой последовательности нажатий клавиш в виде k блоков информации:

  • первый блок информации описывает перемещение от файла с номером 1 к файлу с номером a1;
  • второй блок информации описывает перемещение от файла с номером a1 к файлу с номером a2;
  • …
  • k-ый блок информации описывает перемещение от файла с номером ak–1 к файлу с номером ak.

Каждый блок информации выглядит следующим образом.

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

Следующие L строк блока описывают нажимаемые клавиши. Каждая из строк содержит описание одной клавиши:

  • если нажимается клавиша вниз, то в строке записывается слово down;
  • если нажимается клавиша вверх, то в строке записывается слово up;
  • если нажимается клавиша Alt, то в строке записывается слово Alt;
  • при нажатии клавиши с латинской буквой выводится соответствующая ей латинская буква.

Если существует несколько оптимальных способов перемещения, то требуется вывести любой из них.

Система оценки
  • Подзадача 1. Решения, верно работающие при \(n \leqslant 30\), оцениваются в 28 баллов. Баллы ставятся при прохождении всех тестов.
  • Подзадача 2. Решения, верно работающие при больших ограничениях, оцениваются по 4 балла за тест..
Примеры
Входные данные
6
a
b
c
d
e
f
4
4 3 1 6
Выходные данные
2
Alt
d
1
up
2
Alt
a
1
up
#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
#727
Квас
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

Первая строка входных данных содержит число N – количество городов ( N ≤ 10) и еще N чисел – количество кваса, требуемое ежедневно 1-м, 2-м, …, N -м городом (города нумеруются подряд вдоль кольцевой дороги).

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

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

Задача Е, рис. 4Примеры

Пояснение для второго примера(см. рисунок):

На острове 6 городов, потребность каждого города указана в кружочках, номер города рядом с кружочком.

Если построить завод во 2-м городе (он выделен серым), то потребуется заплатить 4 + 1 (стоимость перевозки в 1-й и 3-й города) + 5*2 + 3*2 (в 4-й и 6-й) + 1*3 (в 5-й см. рисунок).
Во 2-й вообще ничего не везем. Это будет 24 тугрика. Легко проверить, что если построить завод в других городах, сумма будет больше. Например, если построить в 4-м городе, то сумма составит 1 + 1 + 3*2 + 4*2 + 4*3 = 28 тугриков.

Примеры
Входные данные
3 5 3 10
Выходные данные
3
Входные данные
6 4 4 1 5 1 3
Выходные данные
2
#999
Юный поджигатель
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дан граф на клетчатом поле, вершины которого могут находится в целых клетках и соединяться по линиям сетки или по диагонали клеток (в случае пересечения двух клеток там также создается вершина). Необходимо найти вершину, расстояние от которой до самой дальней минимально.

На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.

На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:

  • Спички длины 1 выкладывались по сторонам клеток.
  • Спички длины выкладывались по диагоналям клеток.

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

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

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

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

Во входном файле записано сначала число N — количество спичек (1N40). Затем идет N пятерок чисел вида X1, Y1, X2, Y2, T, задающих координаты концов спички и время ее сгорания при условии, что она будет подожжена с одного конца (гарантируется, что каждая спичка имеет длину 1 или , все спички образуют связную фигуру, и положение никаких двух спичек не совпадает). Все координаты — целые числа, по модулю не превышающие 200, время сгорания — натуральное число, не превышающее 107.

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

Выведите координаты целочисленной точки, в которой нужно поджечь фигуру, чтобы она сгорела за наименьшее время, а затем время, за которое в этом случае фигура сгорит. Время должно быть выведено с точностью не менее 2-х знаков после десятичной точки. Если решений несколько, выведите любое из них.

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