Лягушки, задача про лягушек :) Опции

[Скрытная]

Лягушки
Время на тест: 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

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

Сообщение отредактировано: Скрытная - 22.12.2007 1:07

[Michael_Rybak]

Откуда задача, колись ;)

[andriano]

Ты можешь подсчитать, сколько легушек переправится при одном варианте?
А при другом?
А сравнить эти два числа?
А сравнить числа для бОльшего количества вариантов?

[Michael_Rybak]

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

[Скрытная]

2 Michael_Rybak ну, да... задача олимпиадная... а это имеет какое-то значение?

[Perfez]

[offtop]
Явно палёнка...http://forum.algolist.ru/task/160-zadacha-liagushki.html
Так что,можно со спокойной совестью помогать...
[/offtop]

[Скрытная]

ну и?

[Lapp]

задача олимпиадная... а это имеет какое-то значение?

Безусловно.
Помогать тебе выиграть олимпиаду - не в традициях этого Форума. Если олимпиада уже закончилась - с удовольствием обсудим и поможем решить.
Годится?

[Скрытная]

Годится

Она прошла ещё в 2004 году

Сообщение отредактировано: Скрытная - 24.12.2007 12:49

[Michael_Rybak]

Задача на максимальный поток. Знаешь, что это такое?

[Скрытная]

Про метод знаю, но в нем самом толком не разобралась

[Michael_Rybak]

Ну вот разберись. А потом придумаешь, как его здесь применить.

[Скрытная]

а можно это как-нибудь в двух словах описать? а то я читаю-читаю а понять не могу =\

[Michael_Rybak]

В двух словах - нельзя. Я сам долго понять не мог.

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

И приходи с конкретными вопросами по алгоритму.