Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Очереди

Задачу добавил: alef

Успешно сдано решений: 7

Кафе, которое понравилось M гостям города S, нравится не только им, но также и многим другим гостям и жителям города S. 
Поэтому в обеденный перерыв приходится стоять в очереди. M гостей города S, придя в кафе, увидели там N очередей. Для каждой очереди известно время обслуживания одного
покупателя Ti (i = 1, 2, ..., N), а также Qi - количество людей, находящихся в очереди #i на момент прихода M гостей города S. И теперь они перед выбором - в какие из очередей лучше встать. Дело в том, что они хотели бы пообедать вместе, а горячие блюда довольно быстро остывают. Поэтому M гостей города S
хотят получить свои заказы так, чтобы время, прошедшее от получения заказа первым из них до получения заказа последним
из них, было бы минимально возможным. Заметим, что гости не торопятся, поэтому их не смутит то, что надо будет стоять даже в самой длинной и медленной очереди. Формат входного файла input.txt Первая строка - целые числа M и N, где 1 <= M <= 1000 - количество гостей города S, желающих пообедать вместе 1 <= N <= 10000 - количество очередей в кафе В каждой из следующих N строк указаны целые числа Ti (1 <= Ti <= 100) и Qi (0 <= Qi <= 10000), i = 1, 2, ..., N через пробел -
время обслуживания одного покупателя в данной очереди и количество людей в ней. Формат выходного файла output.txt Первая строка - целое число - минимально возможное время, которое пройдет между выполнением первого и последнего
из заказов M гостей Вторая строка - M целых чисел через пробел - номера очередей, которые им следует занять, упорядоченные по неубыванию. Если решений несколько, выведите любое из них Пример входного файла 3 5 10 8 6 6 7 3 4 0 5 5 Пример выходного файла 7 3 3 5

Сдать задачу

Задать вопрос жюри по этой задаче