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

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

ArtTema

Новый участник

Сообщения: 2
Благодарности: 0

Изменения

Автор: Drongo
Дата: 07-04-2010
Описание: открытый E-Mail запрещён... Пользуйтесь ПМ

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

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

Отправлено: 21:29, 07-04-2010

lxa85

Необычный

Сообщения: 4462
Благодарности: 994

Профиль | Сайт | Отправить PM | Цитировать

Цитата pva:

вот это мне кажется не подходит »

Вполне может быть, т.к. это чистейшее рассуждение вслух. Ну... может быть плюс немного википедии

-------
- Я не разрешаю тебе быть плохой! Потому что плохие люди совершают плохие поступки. А это нехорошо!
(Из наставлений 5 летней девочки своей младшей сестре)

Отправлено: 08:59, 12-04-2010 | #11