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

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

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

 
 Ответить  Открыть новую тему 
> Apelsin
сообщение
Сообщение #1





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

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


3. Мандаринчики
Имя исполняемого файла Mandarin.exe
Имя входного файла Mandarin.in
Имя выходного файла Mandarin.out

Нуржан и Хайрош очень любят путешествовать. Однажды, когда они были в очередной поездке, Нуржан решил залезть на дерево. Забравшись, он увидел под собой мандарины. Для Нуржана мандарины видны, как окружности определенного радиуса. Снизу, на земле, стоит Хайрош. Он может сообщить Нуржану о том, на какой высоте находится тот или иной мандарин. Будем говорить, что мандарин Ai мешает сорвать мандарин Aj, если Ai находится выше Aj, а также расстояние между центрами мандаринчиков строго меньше суммы радиусов соответствующих окружностей. Так как Хайрош очень хорошо разбирается в мандаринах, он уже знает, на сколько вкусен каждый мандарин. Нуржан и Хайрош хотят сорвать ровно К мандаринов так, чтобы суммарная «вкусность» сорванных мандаринов была максимальна. Заметим, что чем больше радиус мандарина, тем больше сил тратит Нуржан, чтобы сорвать его. Он стремится затратить как можно меньше сил. Помогите друзьям выбрать такой порядок срывания мандаринов, при котором вкусность будет максимальна, а сумма радиусов минимальна! Учтите, что нельзя сорвать мандарин, если хотя бы один из мандаринов, мешающих сорвать данный, все еще висит на дереве.
В первой строке входного файла находятся числа N(<=16) и К(<=N), которое обозначает количество мандаринчиков. В последующих N строках находится информация о каждом мандарине, в следующем виде:
X1, Y1, R1, H1, E1
X2, Y2, R2, H2, E2

XN, YN, RN, HN, EN
Первые два числа задают координаты центра мандарина, следующие три – его радиус, высота, на которой он находится, и его «вкусность». Все числа – натуральные, не превосходящие 10000. В каждой строке числа разделены пробелами. Гарантируется, что нет мандаринов на одинаковой высоте, для которых расстояние между их центрами было бы меньше суммы радиусов их окружностей.
В первой строке выведите число, обозначающее суммарную «вкусность». В последующих К строках выведите номера мандаринчиков, в котором их нужно срывать. Мандарины пронумерованы в порядке, в котором они даны во входном файле. Если возможных ответов несколько, выведите любой.

Пример.
Mandarin.in Mandarin.out
5 3 29
3 3 1 10 6 3
4 4 1 15 10 2
5 2 2 21 11 4
9 2 1 22 8
3 8 2 30 8 100 баллов.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

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

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


В каждый момент времени у нас каждый мандарин либо съеден, либо нет. Всего - не больше 2^16 вариантов. Кодируем позиции числами от 0 до 2^N-1. i-й бит числа равен 0, если мандарин i съеден, и 1 - если нет. Начальная позиция - все единички. От каждой позиции переходим к другой, срывая один мандарин, т.е. обнуляя один единичный бит. При этом обнуляем только биты, соответствующие тем мандаринам, которые можно сорвать по условию. Ищем поиском в ширину. Удобно просто обрабатывать все позиции в убывающем порядке; так - можно, потому что, срывая мандарин, мы уменьшаем код позиции.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Профи
****

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

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


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

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

 





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