ArtTema
07-04-2010, 21:29
Здрасте всем!!))
Народ, помогите решить олимпиадную задачку по проге. Бъюсь уже больше недели и всё никак не получается. Она на динамику. Предложите идею в более мение развёрнутом виде или может есть ссылка на разбор(думаю, задача не оригинальная и похожее что-то должно быть в сети, вот только найти у меня, увы, не получилось). Заранее благодарен.)))
Ответы можно ( Отправить в PM (http://www.forum.oszone.net/private.php?do=newpm&userid=240900))
Вот, собственно и она:
«Микрочип»
Время на тест 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
Народ, помогите решить олимпиадную задачку по проге. Бъюсь уже больше недели и всё никак не получается. Она на динамику. Предложите идею в более мение развёрнутом виде или может есть ссылка на разбор(думаю, задача не оригинальная и похожее что-то должно быть в сети, вот только найти у меня, увы, не получилось). Заранее благодарен.)))
Ответы можно ( Отправить в PM (http://www.forum.oszone.net/private.php?do=newpm&userid=240900))
Вот, собственно и она:
«Микрочип»
Время на тест 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