Страница: 1 2 3 4 >> Отображать по:
#31
Роботы
  
ограничение по времени на тест
20.0 second;
ограничение по памяти на тест
64 megabytes
Задан невзвешенный граф. По графу перемещаются роботы, для которых заданы начальные вершины. Требуется определить, через какое время все роботы встретятся в какой либо вершине или середине ребра.

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

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

Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).

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

Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.

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

Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).

Оценка задачи

1 балл получат программы, правильно решающие задачу в случае, когда встреча роботов произойдет в зале, при ограничениях N≤100, K≤2000, M≤100.

Примеры
Входные данные
4 5
1 2
2 3
3 4
1 4
1 3
3
1 2 4
Выходные данные
1
Входные данные
3 2
1 2
2 3
2
1 3
Выходные данные
1
#34
Разрезанный прямоугольник
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

 4
Рисунок, соответствующий 1-му примеру входных и выходных данных

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

Сначала на вход программы поступают два положительных числа X и Y, задающих координаты правого верхнего угла прямоугольника. Прямоугольник расположен в системе координат так, что левый нижний его угол имеет координаты 0,0 и стороны параллельны осям координат.

Далее вводится целое число N — количество разрезов (1≤N≤200). Затем описываются сами разрезы. Каждый разрез делался вдоль некоторой прямой. Каждая прямая, соответствующая разрезу, задается тремя числами A, B, C такими, что все точки (x,y) этой прямой (и только они) удовлетворяют уравнению Ax+By+C=0 (при этом всегда A2+B2>0).

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

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

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

Система оценки

1 балл получат программы, правильно решающие задачу при ограничении 1≤N≤50.

Примеры
Входные данные
5.00 1.00
3
1.00 -2.00 0.00
1.00 -3.00 -2.00
1.00 1.00 -4.00
Выходные данные
3
Входные данные
4.00 2.00
2
1.00 -2.00 0.00
1.00 2.00 -4.00
Выходные данные
4
#423
В школу на велосипеде
  
Источники: [ Командные олимпиады, ВКОШП, 2004, Задача A ]
Даны две пересекающихся окружности. Необходимо найти кратчайший путь от точки до точки по окружностям.

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

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

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

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

Будем считать, что в городе введена прямоугольная декартова система координат.

Первые две строки входных данных описывают велосипедные дорожки. Каждая из них содержит по три целых числа – координаты центра окружности, которую представляет собой соответствующая дорожка, и ее радиус. Координаты и радиус не превышают 200 по абсолютной величине, радиус – положительное число. Гарантируется, что дорожки не совпадают.

Следующие две строки содержат по два вещественных числа – координаты точки, где Петя заезжает на дорожку, и точки, в которой Петя съезжает с дорожки. Гарантируется, что каждая из точек с высокой точностью лежит на одной из дорожек (расстояние от точки до центра одной из окружностей отличается от ее радиуса не более, чем на 10-8). Точки могут лежать как на одной дорожке, так и на разных.

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

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

Если доехать из дома до школы по велосипедным дорожкам невозможно, выведите  число -1.

includegraphics{pics/bike.1} includegraphics{pics/bike.2} includegraphics{pics/bike.3}
Примеры
Входные данные
0 0 5
4 0 3
3.0 4.0
1.878679656440357 -2.121320343559643
Выходные данные
8.4875540166
Входные данные
0 0 5
4 0 3
4.0 3.0
4.0 -3.0
Выходные данные
6.4350110879
Входные данные
0 0 4
10 0 4
4.0 0.0
6.0 0.0
Выходные данные
-1
#425
Военный поход
  
Источники: [ Командные олимпиады, ВКОШП, 2004, Задача C ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В неориентированном графе, где для ребра указана его стоимость, мы владеем некоторым набором ребер. Необходимо купить все дороги по маршруту и продать часть своих дорог.

В одном феодальном государстве средневековой Европы было n городов и m дорог, каждая из которых соединяла некоторые два города. Каждая дорога принадлежала правителю одного из городов (не обязательно одного из тех, которые она соединяла). Однажды правитель города S решил объявить войну правителю города T. Перед ним сразу же встала нелегкая задача: как довести армию до города T.

Правитель каждого города требует плату за проход войск через его город. Кроме того, правитель города S может перемещать войска только по дорогам, которые принадлежат ему. При этом он может купить любую дорогу у ее владельца за определенную плату (даже если владелец – правитель города T). К сожалению, все деньги из казны города S были потрачены на предыдущий неудачный военный поход, поэтому сначала правителю придется продать некоторые свои дороги (разумеется, после этого он не сможет провести по ним войска).

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

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

В первой строке вводятся целые числа n и m – количество городов и дорог соответственно ( 2\( le\)n\( le\)2 000, 1\( le\)m\( le\)50 000). Города нумеруются от 1 до n, города S и T имеют номера 1 и n соответственно.

Следующие n строк содержат под одному целому числу ri – плату за проезд через город i ( 0\( le\)ri\( le\)10 000, r1 = rn = 0).

Далее идут m строк,  задающих описания дорог. Дорога описывается четырьмя целыми числами: ai, bi, pi и ci. Здесь ai и bi – номера городов, которые соединяет дорога, pi – номер города, правителю которого она принадлежит, ci – ее стоимость ( ai\( ne\)bi, 1\( le\)ci\( le\)10 000). По дороге можно перемещаться в обоих направлениях. Любые два города соединены не более, чем одной дорогой.

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

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

Если решения нет, выведите  число -1.

Примеры
Входные данные
3 3
0
1
0
1 2 1 10
2 3 1 10
3 1 2 2
Выходные данные
2 1 2
1 3
1 3
#519
Свет
  
Источники: [ Командные олимпиады, ВКОШП, 2003, Задача D ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дан точечный источник света и многоугольник. Необходимо пройти от заданной точки до ближайшей освещенной точки, не проходя через дом.

В точке (0, 0) координатной плоскости расположена лампочка, которая представляет собой точечный источник света. Неподалеку от лампочки находится дом Пети, который представляет собой выпуклый многоугольник с \(N\) вершинами. Сам Петя находится в точке с координатами (\(x\), \(y\)).

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

Петя может перемещаться по плоскости со скоростью \(v\). Разумеется, Петя не может проходить сквозь дом (хотя он может двигаться по его границе).

Выясните, какое минимальное время требуется Пете, чтобы оказаться в освещенной точке.

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

В первой строке вводятся координаты Пети – два неотрицательных вещественных числа, не превышающих 1000, и его скорость v – вещественное число, 10-2\( \le\) v\( \le\) \(10^4\).

Вторая строка содержит \(N\) – число вершин в многоугольнике, задающем Петин дом ( 3\( \le\)N\( \le\)100). Далее в \(N\) строках вводится по два вещественных числа – координаты вершин многоугольника в порядке их обхода против часовой стрелки. Все координаты неотрицательны и не превышают 1000.

Гарантируется, что входные данные корректны, в частности, многоугольник выпуклый, и никакие три его последовательные вершины не лежат на одной прямой. Также гарантируется, что и Петя, и лампочка находятся снаружи от многоугольника, в частности, не находятся на его границе. Расстояние от точки, где находится Петя, до многоугольника и от начала координат до многоугольника не меньше 10-2, расстояние от Пети до начала координат не меньше 10-2.

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

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

Примеры
Входные данные
3.5 3.5 1.0
4
2.0 0.0
4.0 2.0
2.0 4.0
0.0 2.0
Выходные данные
3.58113883008418967000
Страница: 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест