Разработать программу для автоматического составления расписания работ на заводе.
Условие задачи:
- Дан список сотрудников завода и работ, которые необходимо выполнить
- Для каждой работы известно время необходимое на ее выполнение
- Для каждого сотрудника известна длительность его рабочего дня
- Также известна стоимость выполнения работы каждым сотрудником
- Требуется определить, какие работы должен выполнять каждый из сотрудников, чтобы суммарные затраты были минимальными. При этом суммарное время назначенных сотруднику работ не должно превышать длительность его рабочего дня.
Формат входного файла:
1) Первая строка – числа N, M– количество сотрудников на заводе и количество работ
2) Вторая строка – N чисел R_i – продолжительность рабочего дня i-ого сотрудника
3) Третья строка – M чисел T_j – время выполнения j-ой работы
4) Далее идут N строк, в каждой M чисел С_ij – стоимость выполнения j-ой работы i-ым сотрудником.
5) Все числа целые.
В выходной файл программа должна вывести M чисел n_j – номер работника выполняющего j-ую работу (работники нумеруются с единицы).
Пример входного файла:
2 3
4 5
2 2 1
2 3 4
4 6 8
В данном примере 2 работника с продолжительностью рабочего дня 4 и 5, и 3 работы длительностью 2, 2 и 1
Оптимальным для данного входного теста будет ответ
2 1 1
В процессе решения задачи предполагается создание набора разнообразных тестов. Лучшие из них (самые сложные, на которых ваш алгоритм даёт хорошие результаты) надо будет предоставить для "боя программ". Все команды и жюри пришлют набор таких задач, после чего все программы будут запущены на всех этих тестах - целью команды будет получение минимальной суммарной длины полос по всем тестам за минимальное время (программа должна работать не более минуты на одном тесте, в противном случае её результат не засчитывается). Правила турнира запрещают фиксировать специальное поведение программ для конкретных тестов (т.е. если программа не "решила" конкретную задачу, а "узнала её и выдала заранее известный ответ", то такой её ответ будет аннулирован решением жюри).
Тесты будут разделены на категории, с отдельными баллами за каждую:
- Простая
1<=M, N<=10;
0<=T_i, R_i, C_ij<=100;
- Средняя
1<=M, N<=20;
0<=T_i, R_i, C_ij<=100;
- Сложная
1<=M, N<=50;
0<=T_i, R_i, C_ij<=100;