ЕГЭ_информатика

(А. Богданов) Ваня пишет скрипты для генерации заданий ЕГЭ. Известно время, которое затрачивает Ваня на написание каждого скрипта, и время выполнения скрипта. Запуск очередного скрипта возможен только после окончания выполнения скриптов, которые подготавливают для него данные, т. е. тех, от которых скрипт зависит. Пока скрипт работает, Ваня может писать следующий скрипт, но Ваня не может писать два скрипта одновременно и пишет все скрипты в том порядке, в котором они внесены в таблицу. Компьютер у Вани многоядерный и может обрабатывать много простых скриптов одновременно, без взаимного влияния на общую производительность. Определите минимальное время, через которое может завершиться выполнение всех скриптов при условии, что все независимые друг от друга скрипты могут выполняться параллельно.

Информация о скриптах записана в файле 22-65.xls. Типовой пример организации данных в файле:

В данном случае скрипт 1 можно запустить только через 5 минут после начала работы, он закончит выполняться через 5 + 4 = 9 минут. Скрипт 2 Ваня напишет через 5 + 2 = 7 минут, он сразу начнёт работу и закончит выполняться через 7 + 3 = 10 минут. Таким образом, через 11 минут все скрипты-поставщики данных для процесса 3 уже закончили работу, но сам скрипт 3 Ваня напишет (и сможет запустить) только через 5 + 2 + 7 = 14 мин после начала работы. Этот скрипт закончит выполняться через 14 + 1 = 15 минут. Последний скрипт 4 Ваня напишет через 14 + 4 = 18 мин, он закончит выполняться через 18 + 7 = 25 мин. Ответ: 25.

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Определите, сколько процессов будут активны на 200-й мс после старта первого процесса (т.е., при 200 мс < t < 201 мс) при условии, что все независимые друг от друга процессы могут выполняться параллельно и каждый процесс начинает выполняться сразу, как только для этого есть возможность.

(А. Богданов) В файле 22-60.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

Определите максимальное количество процессов, которые завершатся за 73 мс, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

(А. Кабанов) В файле 22-55.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов -- поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.

В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.

Определите, какое наибольшее количество процессов может быть завершено за первые 60 мс с момента запуска первого процесса.

Типовой пример организации данных в файле:

Пусть нас интересуют процессы, которые завершились в первые 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.

(А. Кабанов) В файле 22-42.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(А. Кабанов) В файле 22-40.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Если процесс B зависит от процесса A, то процесс B может начать выполнение не раньше, чем через 3 мс после завершения процесса A. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы -- время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Определите, за какое минимальное время можно выполнить все процессы. В ответе запишите целое число -- минимальное время в мс.

Типовой пример организации данных в файле:

В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 -- через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2 и 3 мс ожидания, то есть, через 7 мс после старта. Он длится 1 мс и закончится через 7 + 1 = 8 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3 и 3 мс ожидания, то есть, через 11 мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 11 + 7 = 18 мс.

(PRO100 ЕГЭ) В файле 22-30.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B требуется, чтобы был выполнен хотя бы 50% от количества процессов А. Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы -- время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример организации данных в файле:

В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 -- через 3 мс с момента старта. Процесс 3 может начаться только после завершения хотя бы 50% из двух процессов, то есть любого процесса 1 или 2, то есть, через 3 мс после старта. Он длится 1 мс и закончится через 3 + 1 = 4 мс после старта.

Выполнение процесса 4 может начаться только после завершения хотя бы 50% из трёх процессов, то есть любых двух из процессов (1, 2, 3), то есть, через 4 мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 4 + 7 = 11 мс.

(PRO100 ЕГЭ) В файле 22-27.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(Л. Евич) В файле 22-11e.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(Л. Евич) В файле 22-10e.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(Л. Евич) В файле 22-9e.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(Л. Евич) В файле 22-8e.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(Л. Евич) В файле 22-6e.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(Л. Евич) В файле 22-4e.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(В. Шубинкин) В файле 22-4.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2023 года).

(И. Карпачёв) На ленте исполнителя МТ в соседних ячейках записана последовательность из 1000 символов, состоящей из 764 двоек, 122 троек и 114 символов Х, расположенных в указанном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа для исполнителя:

Команды движения каретки: L – влево, R – вправо, S – стоп. Какую десятичную цифру необходимо указать вместо символа Х, чтобы сумма цифр последовательности после выполнения программы равнялась 3496?

(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа для исполнителя:

Команды движения каретки: L – влево, R – вправо, S – стоп. После выполнения программы на ленте осталось 200 нулей. Определите максимально возможное количество единиц, которое могло быть в исходной последовательности.