"Микрочип" - задачка олимпиадного типа
 

Здрасте всем!!))

Народ, помогите решить олимпиадную задачку по проге. Бъюсь уже больше недели и всё никак не получается. Она на динамику. Предложите идею в более мение развёрнутом виде или может есть ссылка на разбор(думаю, задача не оригинальная и похожее что-то должно быть в сети, вот только найти у меня, увы, не получилось). Заранее благодарен.)))
Ответы можно ( Отправить в PM)

Вот, собственно и она:


«Микрочип»

Время на тест 1 секунда



Условие

Микрочип, производимый на некотором заводе, имеет форму плоского квадрата со стороной A микрометров. На нижнюю грань выведены контакты, причем координаты этих контактов в системе координат, в которой оси сонаправлены сторонам чипа, а единичный отрезок имеет длину 1 мкм, являются целыми числами. Для успешной распайки необходимо от каждого контакта протянуть проводящую дорожку к одной из сторон чипа для последующего закрепления на ноге интегральной схемы. Однако используемый технологический процесс позволяет создавать только прямые дорожки, идущие от контакта к краю чипа без изгибов и параллельные сторонам кристалла, причем невозможно проложить одну дорожку под или над другой. Поэтому Вам необходимо определить, в какую сторону выводить каждый из контактов так, чтобы полученные дорожки не пересекались, а суммарная их длина была минимальной.

Входные данные

В первой строке входного файла input.txt находится натуральное A (1 ≤ A ≤ 30) — сторона микрочипа в миллиметрах. Во второй строке находится натуральное N (1 ≤ N ≤ 38) — число контактов на нижней стороне чипа. В последующий N строках следуют пары целых чисел в диапазоне от 1 до A-1 — соответственно абсциссы и ординаты контактов во введенной системе координат.

Выходные данные

В выходном файле output.txt выведите в первой строке число S — минимальную суммарную длину необходимых дорожек. В последующий строках поясните, в какую сторону выводить дорожку для каждого из контактов: в (i+1)-й строке выведите одно из слов UP (англ. «вверх»), DOWN (англ. «вниз»), LEFT (англ. «влево»), RIGHT (англ. «вправо») - направление выведения дорожки i-го контакта.

Пример входных данных



15
15
11 13
6 4
13 3
4 12
5 5
4 9
1 14
3 11
9 7
2 12
1 10
12 2
7 6
8 8
12 1

Пример выходных данных


50
UP
DOWN
RIGHT
UP
LEFT
LEFT
UP
LEFT
RIGHT
LEFT
LEFT
RIGHT
DOWN
UP
DOWN

ArtTema, Есть хоть какое-то решение? Или вы предлагаете писать за вас? :)

Нет, писать я не предлагаю вовсе :) Мне нужна какая-нибудь рабочая идея, алгоритм, который можно было бы реально закодить :) У меня есть некоторые соображения, но они достаточно обстрактны и конкретизировать у меня не получается, вот и обращаюсь за помощью :)

решите врукопашную такую расстановку:
излагай идеи

А это точная формулировка задачи?
Квадрат - это двухмерная фигура, она не может быть ни плоской ни толстой.
Грань - это плоскость у объемной фигуры.

Значит формулировка должна начинаться:
На нижнюю грань микрочипа, имеющую форму квадрата, выведены...

И кроме того:
Если все дорожки должны быть параллельны сторонам чипа, не пересекаться и не изгибаться, то как при таких условиях можно провести дорожку из центра?

Никак, при таких начальных условиях задача не имеет решения.
Там же пример дан, если его нарисовать, то не будет там "заблокированных" контактов.

Точно, чужая иллюстрация меня немного сбила с мысли. Сходу могу предожить такой алгоритм:

1. посчитать "вес" каждой точки - если от нее можно провести дорожку во все стороны, то ее вес = 4, если в три стороны, то ее вес = 3 и т.д.

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

3. если еще есть свободные точки, то перейти к п.1, иначе п.4

4. конец

Но это сходу, врядли это идеальный вариант.

Если требуется режить только заданный пример- это можно сделать и без компьютера. Если требуется разработать программу для решения произвольного примера - придётся рассмотреть все варианты (хотя бы в отладочных целях)

дополняем алгоритм delog:
для каждой точки посчитали списки пар {длина, направление}. Отсортировали списки по длине, количеству элементов. текущее решение будет определяться списком указателей на элементы таблицы для каждой точки.
Дальше либо перебором, либо вертится в голове идея, аналог симплекс-метода, как сформулирую - напишу

Вот ещё пример (отладить вариант delog)

Можно попробовать подключить теорию графов. Критерий планарности/непланарности.
Я бы может предложит считать не вес точки, а "штрафы" т.е. расстояния до края по каждому направлению.
Можно попробовать построить дерево поиска с возвратом. Т
На начальном этапе отсечь тупиковые ветви. Например 2 точки на линии.
Далее рисовать граф, причем мы знает что с чем может быть соединено.
Можно не на каждом, можно для начала через 5/10/15 шагов производить оценку планарности. Т.к. это дорогостоящая операция. Затем конечно сократить кол-во шагов.

О!
Можно попробовать волновой алгоритм. С какой-нибудь его модификацией.
Можно попробовать решить обратную задачу. Т.е. найти минимальный остов.
http://ru.wikipedia.org/wiki/Минимал...стовное_дерево
Дерево Штайнера. http://book.itep.ru/3/stain_tree.htm
Также можно поискать задачи про укладку проводников.

вот это мне кажется не подходит, потому что здесь процесс с блокировками. К примеру вот вроде бы оптимальное решение, но оно не допустимо
а допустимо такое:
применение штрафных функций слабо себя оправдывает, т.к. задача дискретная, гладкость решения от этого не повысится.

подумав-подумав допёрло как можно сделать. Нужно использовать принцип максимума понтрягина
. Пронумеруем контакты в любом порядке и начинаем поочереди их перебирать. За текущее состояние процесса принимаем направление обработанных дорожек + оставшиеся возможные направления необработанных (для каждого направления есть своя цена). Так как требуется найти интегральную цену (разделяемая на части сумма), этим принципом пользоваться можно.
Допустим мы уже сделали несколько ходов и у нас есть список возможных направлений для оставшихся дорожек. Тогда наши последовательные ходы должны быть такими, чтобы обеспечить наименьшее значение интеграла (суммарной цены). Мысленно доводим решение задачи до конца и начинаем раскручивать её обратно. На каждом шаге для контакта N (0<=N<=max(N)) и возможного направления I (0<=I<4) запоминаем рассчитываем наименьшую длину и запоминаем соответсвующую ей распайку контактов. Рассчёт ведётся из соображений, что сначала ни один контакт (из изначально не заблокированных) не заблокирован, потом что идеальный контакт заблокирован, потом что из оставшихся идеальный заблокирован и т.д.
На следующем шаге берём за основу полученные (максимум) 4 состояния, и рассчитываем схему с добавленным контактом. Итого потребуется вычислить (max(N)+1)*4 (возможно недоделанных) схем.