Apelsin Опции

[cristall30]

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 баллов.

[Michael_Rybak]

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

[Malice]

Просто рекурсивный обход дерева, с проверкой какие можно рвать, какие нет..