Петя начал готовиться к ЕГЭ по информатике за два дня до экзамена. Он составил план подготовки ко всем 27 заданиям. Для каждого задания указано время подготовки (в часах) и пререквизиты — задания, которые необходимо освоить раньше. Петя начинает изучать задание сразу, как только все его пререквизиты освоены. Независимые задания Петя учит параллельно (левым полушарием — логику, правым — Python, третьим — ничего, оно спит).
| № |
Задание |
Время (ч) |
Нужно сначала |
| 1 |
Графы и таблицы |
6 |
— |
| 2 |
Таблицы истинности |
8 |
— |
| 3 |
Базы данных |
10 |
9 |
| 4 |
Кодирование Фано |
5 |
— |
| 5 |
Алгоритмы с числами |
7 |
— |
| 6 |
Черепаха/Чертёжник |
8 |
5 |
| 7 |
Кодирование звука |
6 |
4 |
| 8 |
Комбинаторика |
10 |
5 |
| 9 |
Электронные таблицы |
4 |
— |
| 10 |
Поиск в тексте |
3 |
9 |
| 11 |
Объём памяти |
5 |
4 |
| 12 |
Машина Тьюринга |
15 |
5; 2 |
| 13 |
IP-адресация |
6 |
— |
| 14 |
Системы счисления |
8 |
5 |
| 15 |
Логика и тождества |
12 |
2 |
| 16 |
Рекурсия |
14 |
5 |
| 17 |
Обработка посл-тей |
10 |
9; 5 |
| 18 |
Робот-сборщик |
12 |
1; 5 |
| 19 |
Теория игр (1 ход) |
8 |
— |
| 20 |
Теория игр (2 хода) |
10 |
19 |
| 21 |
Теория игр (стратегия) |
12 |
20 |
| 22 |
Параллельные процессы |
8 |
1 |
| 23 |
Исполнитель (ДП) |
14 |
5; 8 |
| 24 |
Обработка строк |
10 |
5; 10 |
| 25 |
Делители и простые |
16 |
5 |
| 26 |
Жадные/DP на массивах |
20 |
5; 8; 16 |
| 27 |
Финальный босс |
24 |
5; 8; 16; 17 |
Петя не обязан готовиться ко всем 27 заданиям — он может пропустить самые сложные. Однако если задание требует пререквизит, Петя обязан его изучить (и он тоже войдёт в число решённых).
Определите минимальное время (в часах), за которое Петя подготовится к решению хотя бы 17 заданий (это примерно 70 тестовых баллов — достаточно для приличного вуза, но это не точно).
Мама Пети подсчитала: если готовиться ко всем 27 последовательно, нужен 271 час. У Пети двое суток. Мама рекомендует расставлять приоритеты.