Задача D. Распределение задач ≡

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

3
1 1 4
5.2 3.4 4
2
1 1 2 5
0.7 1 1.2 1.5

1 2 2