| |
Задача Techno
Про технологію виробництва деякого механізму відомо наступне:
-процес складається з окремих операцій;
-для кожної операції відома її тривалість;
-деякі з операцій вимагають, щоб якісь інші обов'язково були завершені до початку даної (наприклад, перш ніж фарбувати, потрібно завершити шліфувати);
-якщо для пари операцій жодна не вимагає, щоб інша була завершена, ці операції незалежні: їх можна проводити в будь-якому порядку, в тому числі одночасно або так, що час їхнього виконання перекривається частково.
Напишіть програму, яка аналізуватиме опис технологічного процесу і даватиме відповідь на питання:
1. Який час є необхідним, щоб отримати готовий виріб?
2. Які операції є критичними у тому смислі, що навіть невелике збільшення їхньої тривалості призводить до зростання часу, знайденого у пункті 1?
Технічні умови: Програма читає з клавіатури спочатку число N - загальну кількість операцій технологічного процесу, потім код останньої операції процесу; далі йдуть N описів операцій. Кожен такий опис є блоком наступного формату: спочатку записані код цієї операції, її тривалість та кількість тих операцій, що мусять бути завершені до початку даної, потім список кодів цих операцій. Зокрема, якщо операція не вимагає, щоб якісь інші операції були завершені, третє число блока дорівнює 0 (і виявляється останнім у блоці).
Програма повинна вивести на екран спочатку час, необхідний для отримання готового виробу, а потім (у довільному порядку, але обов’язково без повторів) перелік кодів критичних операцій; перелік має завершуватися переведенням рядка (негайно після останнього коду переліку).
Якщо заданий у вхідних даних технологічний процес неможливий, вихід має містити єдине число –1.
Загальна кількість операцій 2<=N<=1000. Код операції - ціле число з діапазону від 0 до 30 000; тривалість операції - натуральне число, не більше 106.
Введення
3 3 1 4 0 2 6 1 1 3 3 1 2
Виведення
13 1 2 3
Введення
4 4 0 10 0 20 12 0 4 3 3 0 20 50 50 20 0
Виведення
23 50 4
Задача Techno
О технологии производства некоторого механизма известно следующее:
-процесс состоит из отдельных операций;
-для каждой операции известна её длительность;
-некоторые из операций требуют, чтобы некоторые другие обязательно были завершены до начала данной (например, перед тем как красить, необходимо завершить шлифовку);
-если для пары операций ни одна не требует, чтобы другая была завершена, эти операции независимы: их можно проводить в любом порядке, в том числе одновременно или так, что время их выполнения пересекается частично.
Напишите программу, анализирующую описание технологического процесса и находящую ответ на вопросы:
1. Какое время необходимо, чтобы получить готовое изделие?
2. Какие операции критичны в том смысле, что даже небольшое увеличение их длительности приводит к увеличению времени, найденного в пункте 1?
Технические условия: Программа читает с клавиатуры сначала число N - общее количество операций технологического процесса, потом код последней операции процесса; потом идут N описаний операций. Каждое такое описание является блоком следующего формата: сначала записаны код этой операции, её длительность и количество тех операций, которые должны быть завершены до начала данной, потом список кодов этих операций. В частности, если операция не требует, чтобы какие-либо другие операции были закончены, третье число блока равно 0 (и оказывается последним в блоке).
Программа должна вывести на экран сначала время, необходимое для получения готового изделия, а потом (в произвольном порядке, но обязательно без повторов) перечень кодов критических операций; перечень должен завершаться символом перевода строки (сразу же после последнего кода перечня). Если заданный во входных данных технологический процесс невозможен, вывод должен содержать единственное число –1.
Общее количество операций 2 ≤ N ≤ 1000. Код операции - целое число из диапазона от 0 до 30 000; длительность операции - натуральное число, не превышающее 106.
Ввод
3 3 1 4 0 2 6 1 1 3 3 1 2
Вывод
13 1 2 3
Ввод
4 4 0 10 0 20 12 0 4 3 3 0 20 50 50 20 0
Вывод
23 50 4
|
|
