Олимпиадные задачи, (переименовано) Опции

[Reflex]

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

задача 1.
При игре в лапту одна команда ловит мяч и пытается осалить им бегущего. Игрок другой команды должен, перед тем как бежать, ударить мяч в поле. Известно, на какое максимальное расстояние он может ударить, а также скорости и начальные координаты игроков другой команды. Требуется выбрать направление и силу удара так, чтобы минимальное время, которое потребуется другой команде, чтобы поднять мяч с земли, было наибольшим. (Пока мяч летит, игроки стоят на местах.)
Формат входных данных
В первой строке входного файла записаны два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, D ≤ 1000, N ≤ 200). В следующих N строках записаны по три числа – начальные координаты xi и yi и максимальная скорость vi соответствующего игрока (скорости и координаты — целые числа, –1000 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000, 0 < vi ≤ 1000), никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (y  0).
Формат выходных данных
В выходной файл выведите сначала время, которое потребуется игрокам, чтобы добежать до мяча, а затем координаты точки, в которую нужно выбить мяч. Если таких точек несколько, выведите координаты любой из них. Время и координаты нужно вывести с точностью 10–3.




//-----------------------------------------------------------------------------------------------------------------------------------


задача 2


По двум однополосным дорогам едут машины. На перекрестке эти дороги сливаются в одну однополосную (машины едут как раз в ее сторону). На этом самом перекрестке стоит постовой милиционер, который регулирует движение, а именно, выбирает, с какой из двух дорог в данный момент машины будут заезжать.
В каждый момент времени либо одна из дорог является "активной", т.е. перекресток проезжают машины с этой дороги, либо регулировщик производит переключение потока на другую дорогу (в этот момент никакие машины через перекресток не едут). На то, чтобы "переключить" поток, тратится время Т.
В некоторый момент образовалась пробка. На 1-й дороге скопилось N машин, а на 2-й — M. Для каждой машины известно время, которое ей потребуется для проезда развилки, если она первая в очереди и ее дорога "активна".
Требуется разработать план действий для постового по переключению потоков, при котором среднее время ожидания машины минимально (временем ожидания машины называется время с момента образования пробки до того момента, когда данная машина заканчивает проезжать перекресток; для вычисления среднего времени суммируются времена ожидания всех машин и полученная сумма делится на общее количество машин). В начальный момент активна первая дорога.
Формат входных данных
Во входном файле записаны сначала числа T, N и M, затем N чисел — времена проезда перекрестка машинами с первой дороги (в порядке удаления от перекрестка), а затем M чисел — времена проезда перекрестка машинами со второй дороги.
Все числа в файле целые неотрицательные, все времена не превосходят 100, T ≤ 100, N, M ≤ 1000, N+M > 0.
Формат выходных данных
В первой строке выходного файла выведите одно число — минимальное среднее время ожидания c точностью 10–3. Далее выведите информацию о машинах в порядке их проезда перекрестка и о переключении потока в следующем формате. Для каждой машины выведите информацию в формате:
Сar k from road i
где k — номер машины на своей дороге (ближайшая к перекрестку в момент образования пробки машина имеет номер 1, следующая на той же дороге — 2 и т.д.), i — номер дороги: 1 или 2.
Для каждого переключения потока выведите информацию:
Switch road from 1 to 2
для переключения потока с первой дороги на вторую или
Switch road from 2 to 1
для переключения потока со второй дороги на первую. Информация обо всех событиях (переключениях и проездах через перекресток) должна выводиться именно в том порядке, в котором они происходят.
Если решений несколько, выведите любое из них.
Пример
cars.in
1 2 2
5 6
1 7
cars.out
11.500
Switch road from 1 to 2
Car 1 from road 2
Switch road from 2 to 1
Car 1 from road 1
Car 2 from road 1
Switch road from 1 to 2
Car 2 from road 2

Сообщение отредактировано: volvo - 27.10.2006 16:36

[volvo]

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

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

[Michael_Rybak]

Очень милые задачки. Первая решается бинарным поиском, вторая - динамикой.

[Reflex]

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

[Michael_Rybak]

Что значит "гораздо похитрее"? Она решается бинарным поиском по времени, которое потребуется другой команде, чтобы поднять мяч с земли. Фиксируем время, дальше - ничего особо хитрого.

[Reflex]

ну попробуй реализовать так, но не думаю что получиться

[Michael_Rybak]

Пробовать я буду разве что из интереса. То, что так - получится, я знаю точно. Это далеко не самая сложная задача, чтобы я сомневался ;)

Если у тебя есть тесты, и ты их выложишь, или тесты есть в каком-нибудь онлайн архиве - напишу для интереса. Кодить мне тут от силы 15 минут.