Так как рассылка на subscribe.ru откралась не давно, а студенческий конкурс
уже идет, то следующие несколько рассылок будут содержать старые письма.
-------------------
Этой рассылкой мы начинаем первый тур второго конкурса по машинному
программированию среди студентов.
Ниже приведена задача первого тура
Задача риэлтера
Есть несколько человек желающих продать, купить или обменять
квартиры. Риэлтер должен помочь им в этом и сам остаться с прибылью.
Все обмены осуществляются через продажу старых квартир и покупку
новых.
ТЕХНИЧЕСКОЕ ЗАДАНИЕ
Все данные хранятся в файле exchange.txt. В каждой строке файла
записана информация ровно об одном обмене. Строке содержится
информация в описанном ниже порядке.
<пробелы>
<номер обмена>
<пробелы>
<количество комнат первой продаваемой квартиры><пробелы><её цена>
','
<количество комнат второй продаваемой квартиры><пробелы><её цена>
','
...
<количество комнат последней продаваемой квартиры><пробелы><её цена>
';'
<пробелы>
<максимальная сумма доплаты>
<пробелы>
'='
<пробелы>
<количество комнат первой желаемой квартиры><пробелы><её цена>
','
<количество комнат второй желаемой квартиры><пробелы><её цена>
','
...
<количество комнат последней желаемой квартиры><пробелы><её цена>
';'
<пробелы>
<минимальная сумма выручки>
ЦЕЛЬ
Найти цепочку взаимных обменов выгодную для риэлтера. Выдать в файл
output.txt последовательность номеров обмена, каждый номер в своей
строке.
ПРИМЕР
В файле exchange.txt
20 1 300, 2 400; 0 = 3 600; 0
10 2 500, 1 200, 3 700; 0 = ; 1400
12 5 1100; 100 = 1 200, 1 200, 2 400; 0
1 5 1000; 0 = ; 1100
2 ; 1305 = 4 1100; 0
В файле output.txt
20
10
12
1
ЗАДАНИЕ 1
Написать программу для выполнения цели, которая описана выше.
ЗАДАНИЕ 2
Предоставить пару файлов (exchange.txt, output.txt) - тест, для
проверки задания 1.
ОЦЕНКА ЗАДАНИЙ
Оценка задания 1 соревновательная. Чем более выгодную цепочку
обмена находит Ваша программа, тем больше баллов она получает.
Максимальное количество баллов за это задание - 50.
Сама проверка будет проводиться в два этапа.
На первом этапе программы будут проверяться на тестах жюри.
Программы, удовлетворяющие требованиям, будут допущены ко второму
этапу. Максимальное количество баллов за это задание - 50.
Второй этап - проверка программ на тестах участников. Тесты второго
задания будут получать тем больше баллов, чем ближе количество
прошедших его программ к половине. Тест участника получает ноль
баллов, если его ни проходит никто или проходят все. Тест участника
снимается с соревнования, если программа этого участника не проходит
свой тест.
КОМАНДНЫЙ ВАРИАНТ
Решать эту задачу можно командой. В команде должно быть не более 4
человек. За каждого члена команды будут даваться дополнительные баллы.
Команда из двух человек получает дополнительно 5 балла, из трёх - 10
балов, из четырёх - 15 баллов. Каждый член команды получит все баллы,
набранные командой, включая призовые. Все члены команды должны
участвовать во втором туре, иначе командные баллы могут быть потеряны.
БАЛЛЫ
50 баллов за первое задание, 50 баллов за второе задание и 15
баллов за команду из четырёх человек. Итого один участник (каждый в
команде) может получить до 115 баллов.
Автор задачи: В.В.Пупышев
25 ноября 2002 последний день присылать решения.
18 ноября 2002 последний день задавать вопросы по формулировке
задачи.
Вопросы по задаче посылайте на адрес жюри: grantadmin@mark-itt.ru
До свидания.
Жюри олимпиады "МАРК"
e-mail: grantadmin@mark-itt.ruhttp://colymp.da.ru
01.11.2002