Задача 6A. Распределение задач

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб
Максимальный балл:10000  

Условие

Группа разработчиков работает над проектом. Весь проект разбит на задачи, для каждой задачи указывается ее категория сложности (1, 2, 3 или 4), а также оценочное время выполнения задачи в часах. Проект считается выполненным, если выполнены все задачи. Для каждого разработчика и для каждой категории сложности задачи указывается коэффициент, с которым, как ожидается, будет соотноситься реальное время выполнения задачи данным разработчиком к оценочному времени. Считается, что все разработчики начинают работать с проектом в одно и тоже время и выделяют для работы одинаковое время. Необходимо реализовать программу, распределяющую задачи по разработчикам, с целью минимизировать время выполнения проекта (получить готовый проект за минимальный промежуток времени). Поиск решения необходимо реализовать с помощью генетического алгоритма.

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Решение набирает количество баллов, вычисляемое по следующей формуле: Score = 106Tmax. Tmax — наибольшее среди всех разработчиков время, затраченное на выполнение выданных соответствующему разработчику задач.

Формат входного файла

Первая строка входного файла содержит целое число N количество задач.

Вторая строка — N целых чисел от 1 до 4 категорий сложности задач.

Третья строка — N вещественных положительных чисел оценочного времени для задач.

Четвертая строка – целое число M, количество разработчиков .

Следующие M строк содержат по 4 вещественных положительных числа — коэффициенты каждого разработчика.

Формат выходного файла

Первая и единственная строка выходного файла содержит N целых чисел wi — номер разработчика, назначенного на i - ю задачу.

Ограничения

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 1 4
5.2 3.4 4
2
1 1 2 5
0.7 1 1.2 1.5
1 2 2

0.070s 0.015s 17