Задача первого дня

При решении NP-полных задач, во-первых, может оказаться, что какой-то экспоненциальный алгоритм работает приемлемое время на реальных данных; во-вторых, можно пытаться найти (за полиномиальное время - в худшем или в среднем) не оптимальное решение, а некоторое приближение к нему. На практике такое близкое к оптимальному решение может быть вполне достаточным. Алгоритмы, дающие такие решения, называют приближенными алгоритмами.
Удобно оценивать качество алгоритма, измеряя относительную ошибку. Пусть мы решаем оптимизационную задачу: ищем объект с наибольшей или наименьшей стоимостью среди множества объектов, на которых задана функция стоимости.
Относительная ошибка определяется (для каждого входа алгоритма) как отношение

Задан набор городов в виде неориентированного графа. Коммивояжер должен объехать все города, побывав в каждом ровно по одному разу, и вернуться в город, из которого начато путешествие. Города нумеруются целыми числами от 0 до N-1 (1 <= N <= 400), начиная с города, из которого коммивояжер стартует. Известно, что перелет из города i в город j стоит
c(i,j) рублей (считаем цены целыми положительными числами, c(i,j) = c(j,i)). Большинство, но не обязательно все, цены пропорциональны геометрическим расстояниям между городами. Требуется разработать и реализовать приближенный алгоритм, осуществляющий поиск пути наименьшей стоимости. Исполнение программы должно занимать не более N*N*0.01 сек. На чтение входных данных отводится N*N*0.01 сек. (но не менее 2 сек.). Результаты будут сравниваться по относительной ошибке по сравнению с точным решением.

Входные данные: В первой строке файла input.txt записано число N - количество городов. Каждая следующая строка содержит по три целых числа, записанных через некоторое количество пробелов - номера городов и стоимость перелета между ними. Строка может начинаться с пробела. Граф не обязательно полный, наличие гамильтонова цикла гарантируется. Задача не требует проверки корректности входных данных.

Выходные данные: Файл output.txt должен содержать в первой строке одно целое число - стоимость найденного пути. Во второй строке должен быть приведен сам путь - перечисление вершин, начиная с 0.

Задача второго дня

Перед вами стоит задача: навести порядок в архиве изображений ftp-сайта. Архив собирался много лет и состоит из изображений реальных сцен - пейзажей, животных, людей, репродукций картин. Изображения получены разными способами: цифровой фотографией, сканированием обычных фотографий, оцифровкой видео- и кинокадров. Изображения хранятся в формате JPG.
Задача состоит в том, что среди изображений много дубликатов - снимков одной и той же сцены с одного и того же ракурса, или просто копий одного и того же изображения. Основная же проблема при решении этой задачи состоит в том, что копии подвергались различной обработке: упаковке алгоритмом JFIF с различными параметрами, масштабированию (иногда с нарушением отношения высоты к ширине), цифровому ретушированию и цветокоррекции (иногда весьма непрофессионально), добавлению различных логотипов и рамок, обрезанию краев, преобразованию в 256 цветов с диффузией ошибки и без и повторному сжатию. Кроме того, сканированные и оцифрованные кадры могли сканироваться с оригиналов различного качества в различном разрешении и с различными настройками сканера по яркости, контрастности и цветопередаче. Все это приводит к тому, что бинарное сравнение изображений (как упакованных, так и распакованных) ни в коем случае не может служить критерием их одинаковости.
Вам дана случайная выборка изображений из архива (до 30% его объема). Ваша задача - написать программу, которая будет просматривать весь архив, и выдавать список файлов, которые она сочтет дубликатами. Вам предоставляется библиотека libjpeg для работы (распаковки, упаковки и других преобразований) с изображениями формата JPG с полной документацией. Кроме того, вы можете пользоваться программами Adobe Photoshop и AcdSee для просмотра и редактирования изображений.

Формат ввода и вывода: Первым аргументом командной строки программе передается имя каталога, в котором лежат изображения. Каталог может содержать до 15.000 изображений, но не содержит подкаталогов. Каждое изображение хранится в отдельном файле с расширением .JPG. На имена файлов распространяются ограничения MSDOS: имя не более 8 символов и содержит только алфавитно-цифровые символы ASCII и символы _ и ~. Вторым аргументом передается имя файла, в который следует выдать список дубликатов. Список имеет форму текстового файла, в котором каждая группа дубликатов перечислена в одной строке. Имена файлов приводятся без каталога и расширения, разделяются пробелом. Строки разделяются парой символов Cr-Lf. Допустимо, чтобы один и тот же файл встречался во многих группах дубликатов.

Ограничения: Программа должна представлять собой консольное приложение Win32. Программа исполняется на компьютере с ОС Windows NT 4.0 sp 6 с 32 MB оперативной памяти. Объем своп-файла ограничен 1Gb. Кроме того, ваша программа может создать неограниченное количество промежуточных файлов общим объемом не более 1Gb (не считая исходных изображений). Астрономическое время исполнения программы - не более 10мс*N+1мс*N*N (где N - количество изображений).
Соревнования проводятся в двух номинациях: на наибольшую точность поиска дубликатов без учета времени и на наименьшее время исполнения при точности поиска не менее 75%.

Дополнение: Некоторые изображения очень низкого качества (сканировались с низкокачественных оригиналов и/или подвергались многократному редактированию с последующей переупаковкой JPEG). Кроме указанных в условии изображений, архив содержит также файлы, не являющиеся изображениями реальных сцен - фоновые картинки веб-страниц, фракталы, контурные рисунки. Ошибочное признание таких изображений за дубликаты друг друга и даже за дубликаты "нормальных" изображений не считается ошибкой при определении точности поиска.