Войти
или
Зарегистрироваться
Маркетплейс
Курсы
Учебник
Учебник 2.0
ЕГЭ
ОГЭ
Олимпиады
Рубрикатор
Компилятор
Онлайн Компилятор
Компилятор Python с отладкой
Питон - Черепашка
Эмулятор исполнителя Робот - Кумир
Редактор HTML Code
SQLite Studio - работа с БД
Клавиатурный тренажёр программиста
Олимпиадный тренинг
Задача
.
ege-22_K_26
Задача
Темы:
В файле содержится информация о совокупности
N
вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс
B
зависит от процесса
A
, если для выполнения процесса
B
необходимы результаты выполнения процесса
A
. В этом случае процессы могут выполняться
только последовательно
.
Если процесс
B
зависит от процесса
A
, то процесс
B
может начать выполнение
не раньше
, чем через
5
мс после завершения процесса A
.
Информация о процессах представлена в файле в виде таблицы. В
первом столбце
таблицы указан идентификатор процесса (
ID
), во
втором столбце
таблицы – время его выполнения в миллисекундах, в
третьем столбце
перечислены с разделителем «
;
»
ID
процессов, от которых зависит данный процесс. Если процесс является
независимым
, то в таблице указано значение
0
.
Определите, какое
наибольшее
количество процессов может быть завершено за первые
40
мс с момента запуска первого процесса.
Типовой пример организации данных в файле:
ID процесса
B
Время выполнения процесса
B (мс)
ID процесса(ов)
A
1
4
0
2
3
0
3
1
1; 2
4
7
3
Пусть нас интересуют процессы, которые завершились в первые 6 мс. В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 – через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс и закончится через 5 + 7 = 12 мс. За первые 6 мс успеют завершиться процессы 1, 2, 3. Ответ для этого примера: 3.
ФАЙЛ К ЗАДАНИЮ
1000
ms
256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач
Статистика успешных решений по компиляторам