Автор: Скрытная 22.12.2007 5:05
Цитата
Лягушки
Время на тест: 3 секунды
Как-то раз собрались лягушки в путешествие, как говорится, мир повидать и себя показать. Долго они шли и наткнулись на реку, через которую надо было переправится. Река представляет собой две параллельные прямые. В этой речке (между этими двумя прямыми) есть N кочек, по которым лягушки могут прыгать, но дело в том, что после того как лягушка прыгнула на кочку, она сразу тонет, т.е. прыгать по ней больше нельзя. Кочки представляют собой точки с координатами (Xi, Yi). Но дело в том, что каждая лягушка может прыгать не более чем на расстояние R. Первоначально лягушки располагаются на первом берегу (на первой прямой) и могут начинать прыгать с любой точки прямой, аналогично и заканчивать они могут в любом месте второго берега (в любой точке второй прямой) . Вам необходимо переправить максимальное количество лягушек. Гарантируется что расстояние между прямыми больше числа R.
Ограничения и уточнения:
0 < N < 300
-1000 < A1, A2, B1, B2, C1,C2 < 1000
0 < R < 1000
Гарантируется, что все точки находятся между этими двумя прямыми.
Все вещественные числа вводятся с точность до двух знаков после точки.
Никакие две точки не имеют одинаковые координаты.
Входные данные: InPut.txt
В первой строке три вещественных числа A1,B1,C1 – коэффициенты первой прямой
Во второй строке три числа - A2, B2, C2 – коэффициенты второй прямой
В третьей 2 числа – целое N и вещественное R
Далее идут N строчек - координаты кочек(точек) Xi Yi
Выходные данные: OutPut.txt
В первой строке одно число M – количество переправленных лягушек.
Далее идет M строк – описание пути каждой лягушки:
Первое число Ki – количество использованных кочек, далее Ki чисел – номера этих кочек в том порядке, в котором лягушка по ним прыгала.
InPut.txt OutPut.txt
0 1 0 3
0 1 –5 2 2 4
6 2.25 2 1 3
1 2 2 6 5
3 2
3 3
3 4
4 4
5 2
вот считаю расстояние между кочками и до берегов, соответственно знаю куда какая лягушка может прыгать... но как из всех вариантов выбрать один, так чтобы переправить наибольшее количество лягушек? =\
Автор: andriano 22.12.2007 14:26
Ты можешь подсчитать, сколько легушек переправится при одном варианте?
А при другом?
А сравнить эти два числа?
А сравнить числа для бОльшего количества вариантов?
Автор: Michael_Rybak 22.12.2007 16:12
andriano, задача явно олимпиадная, поэтому сначала пусть автор ответит, откуда она.
Автор: Скрытная 22.12.2007 18:17
2 Michael_Rybak ну, да... задача олимпиадная... а это имеет какое-то значение?
Автор: Perfez 22.12.2007 18:33
[offtop]
Явно палёнка...http://forum.algolist.ru/task/160-zadacha-liagushki.html
Так что,можно со спокойной совестью помогать...
[/offtop]
Автор: Lapp 24.12.2007 10:44
Цитата(Скрытная @ 22.12.2007 14:17)
задача олимпиадная... а это имеет какое-то значение?
Безусловно.
Помогать тебе выиграть олимпиаду - не в традициях этого Форума. Если олимпиада уже закончилась - с удовольствием обсудим и поможем решить.
Годится?
Автор: Скрытная 24.12.2007 16:49
Годится
Она прошла ещё в 2004 году
Автор: Michael_Rybak 24.12.2007 17:14
Задача на максимальный поток. Знаешь, что это такое?
Автор: Скрытная 24.12.2007 17:21
Про метод знаю, но в нем самом толком не разобралась
Автор: Michael_Rybak 24.12.2007 17:24
Ну вот разберись. А потом придумаешь, как его здесь применить.
Автор: Скрытная 24.12.2007 18:45
а можно это как-нибудь в двух словах описать? а то я читаю-читаю а понять не могу =\
Автор: Michael_Rybak 24.12.2007 19:09
В двух словах - нельзя. Я сам долго понять не мог.
Это сложная задача, настройся на несколько дней работы, если тема для тебя нова, и ты собираешься основательно разобраться.
И приходи с конкретными вопросами по алгоритму.