АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1850. Обработка видео

Ограничение времени: 7 сек.
Ограничение памяти:1048576 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

С видеокамеры поступают кадры. Они помещаются в общую очередь на обработку на видеокарте. Известен момент времени появления каждого кадра в этой очереди. Каждый кадр должен пройти через обработку на одной из видеокарт, после чего результат обработки отправляется клиенту.

Всего имеется N видеокарт, каждая из которых обрабатывает кадр за T мс. Одновременно одна видеокарта не может обрабатывать больше одного кадра. Если все видеокарты заняты, то кадр в начале очереди ждёт, пока одна из карт не освободится.

Результаты обработки кадров со всех видеокарт помещаются во вторую общую очередь, которая обрабатывается отдельным процессом по следующему принципу. Пока очередь пуста, процесс ждёт появления первого результата. Как только результат появляется, процесс тут же начинает передавать его клиенту. Время передачи составляет V мс. Соответственно, через V мс после начала передачи процесс будет готов передавать следующий результат.

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

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

В первой строке записаны 4 числа через пробел:

  1. F (1 ≤ F ≤ 105) – количество кадров для обработки.
  2. N (1 ≤ N ≤ 10) – количество видеокарт.
  3. T (1 ≤ T ≤ 100) – время обработки кадра на видеокарте.
  4. V (1 ≤ V ≤ 100) – время на передачу результатов обработки клиенту.
В следующих F строках записано по одному числу X (1 ≤ X ≤ 109) – времена появления кадров. Все времена различны и даны в порядке возрастания.

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

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

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

После вывода каждого ответа программа должна выполнить операцию flush (см. примечание ниже).

Примеры

Входные данные
4 2 10 100
1
2
500
510
Выходные данные
111
211
610
710
Входные данные
8 2 5 1
1
2
3
4
500
510
520
530
Выходные данные
7
8
12
13
506
516
526
536

Примечание

Операция flush (сброс данных из буфера в поток) для разных языков выполняется следующим образом:

  • c++ с библиотекой iostream: std::cout « std::flush; либо std::cout « std::endl; (во втором варианте – также перевод строки)
  • c++ с библиотекой stdio.h: fflush(stdout);
  • pascal: flush(output);
  • java: PrintWriter out = new PrintWriter(System.out); ... out.flush();
  • C#, Visual Basic: Console.Out.Flush()
  • Python: import sys ... sys.stdout.flush()

Условия всех задач турнира (pdf)


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XXI межвузовская олимпиада /
1849. D - Криптография 1850. 1851. F - Треугольник Паскаля 1852. G - Кратчайший путь 1853. H - Двоичное дерево
 
время генерации 0.062 сек.
© Copyright ВоГУ, АВТ, Носов Д.А.