IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Лягушки, задача про лягушек :)
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Катерина

Репутация: -  0  +


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


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

Сообщение отредактировано: Скрытная -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 13)
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Откуда задача, колись ;)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Ты можешь подсчитать, сколько легушек переправится при одном варианте?
А при другом?
А сравнить эти два числа?
А сравнить числа для бОльшего количества вариантов?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


andriano, задача явно олимпиадная, поэтому сначала пусть автор ответит, откуда она.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Катерина

Репутация: -  0  +


2 Michael_Rybak ну, да... задача олимпиадная... а это имеет какое-то значение? unsure.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 231
Пол: Женский

Репутация: -  6  +


[offtop]
Явно палёнка...http://forum.algolist.ru/task/160-zadacha-liagushki.html yes2.gif
Так что,можно со спокойной совестью помогать... smile.gif
[/offtop]
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Катерина

Репутация: -  0  +


ну и? smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Скрытная @ 22.12.2007 14:17) *

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Катерина

Репутация: -  0  +


Годится smile.gif

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

Сообщение отредактировано: Скрытная -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Задача на максимальный поток. Знаешь, что это такое?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Катерина

Репутация: -  0  +


Про метод знаю, но в нем самом толком не разобралась
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ну вот разберись. А потом придумаешь, как его здесь применить.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Катерина

Репутация: -  0  +


а можно это как-нибудь в двух словах описать? rolleyes.gif а то я читаю-читаю а понять не могу wacko.gif =\
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

И приходи с конкретными вопросами по алгоритму.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 22:43
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name