Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Справочная служба

Новый оператор услуг мобильной связи (далее – провайдер) вводит справочную службу, в которой на звонки абонентов будут отвечать сотрудники (далее – операторы) О1, О2, …, Оk. Для дозвона абоненты используют одинаковый для всех телефонный номер. Звонок поступает к свободному оператору с наименьшим порядковым номером (индексом). Этот оператор начинает разговор с абонентом сразу после поступления звонка. В случае, если все операторы заняты, то абонент повторяет попытки связаться со справочной службой и прекращает повторные дозвоны, застав оператора свободным или выполнив определенное (максимальное) количество дозвонов. В последнем случае будем считать, что абонент не дозвонился до справочной службы.

Провайдер приобрел у конкурентов журнал работы справочной службы за один день, в котором указывалась время первого звонка абонента в справочную службу и время, необходимое для разговора. Для принятия решения об оптимальном количестве операторов необходимо с помощью компьютерной программы смоделировать процесс работы справочной службы  и определить интересующие провайдера характеристики.

Известно, что:

·          К – количество операторов, работающих в справочной службе;

·          Z – время, необходимое абоненту для выполнения повторного дозвона;

·          N – максимальное количество повторных дозвонов;

·          в начальный (нулевой) момент времени все операторы свободны;

·          среди нескольких одновременных звонков в первую очередь обрабатывается звонок того абонента, который раньше других был зарегистрирован в журнале справочной службы;

·          оператор после окончания разговора с одним абонентом через ненулевой интервал времени может начинать разговор с другим абонентом.

Необходимо определить:

·          R1 – количество не дозвонившихся абонентов;

·          R2 – среднее количество занятых операторов;

Выражение для расчета R2 имеет следующий вид:

R2 = (m0t0+m1t1 + m2t2 + … + mptp + mp+1tp+1)/T,

·          где ti – время, в течение которого были заняты mi операторов
(m0= mp+1 =0);

·          T = t1 + t2 + … + tp;

·          p – число, показывающее сколько раз изменялось количество занятых операторов.

Входные данные:

Входной файл input.txt описывает журнал работы справочной службы. В первой строке записаны три целых числа: K – количество операторов, работающих в справочной службе; Z – время, необходимое абоненту для выполнения повторного дозвона, и N – максимальное количество повторных дозвонов. Вторая строка содержит число L – количество звонивших абонентов. Каждая из L последующих строк служит для описания очередного звонившего абонента и содержит два целых числа: a – время первого звонка абонента в справочную службу, b – время, необходимое для разговора с оператором. Все строки файла, начиная с третьей, упорядочены по неубыванию времени звонка абонента в справочную службу.

Ограничения:

Все числа целые

1 ≤ K ≤ 1000, 1 ≤ Z ≤ 20000, 1 ≤ N ≤ 70, 1 ≤ L ≤ 10000.

1 ≤ a ≤ 1000000, 1 ≤ b ≤ 1000000.

Выходные данные:

Выходной файл output.txt должен содержать одну строку с двумя искомыми числами R1 и R2,  причем значение R2 необходимо вывести с точностью до трех знаков после точки.


Примеры:
input.txt output.txt
1 2 10 3
10
30 50
65 35
90 85
120 50
125 45
125 30
140 75
150 35
190 70
230 15
3 1.478

Сложность задачи: 50%



Проверку могут осуществлять только зарегистрированные пользователи!


Разбор задачи

Задача решается простым моделированием работы справочной службы. Схематично алгоритм выглядит так:

1)      Поступает первый или повторный звонок абонента с номером m и временем t

2)      Переводим в статус свободных всех операторов, у которых время окончания разговора меньше чем t.

3)      Если есть свободный оператор, то привязываем этому оператору текущего абонента, если же все операторы заняты, то смотрим количество повторных звонко этого абонента. Если это количество не превышает N, то увеличиваем количество повторных звонков абонента и добавляем в общую очередь звонков с временем звонка t + Z, если же количество повторных звонков равно N, то считаем, что абонент не дозвонился.

4)      Повторяем последовательно пункты 1,2,3 до тех пор, пока не будут обработаны все звонки абонентов.

Легко заметить, что R2 равняется сумме времени разговоров всех дозвонившихся абонентов деленное на разницу во между временем окончания последнего разговора и временем начала первого разговора.

Для полного решения задачи необходимо очередь звонков и очередь окончания разговоров для операторов реализовать на базе очереди с приоритетами. Общая сложность алгоритма O(N*L*Log(L) + L*Log(K))

Показать обсуждение


На сайте гостей 22, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]