Процесор

Як відомо, більшість процесорів, які зараз випускаються, є багатоядерними, тобто підтримують виконання декількох інструкцій одночасно. Компанія Paraltel розробила новий тип двоядерного процесора, який дозволяє виконувати $26$ різних інструкцій, які позначаються великими латинськими літерами. Виконання кожної такої інструкції вимагає рівно одного такту роботи процесора.

Програма для цього процесора являє собою послідовність інструкцій. Інструкції програми повинні бути виконані у тому порядку, у якому вони йдуть у програмі, змінювати місцями інструкції не дозволяється.

Завдяки наявності двох ядер, процесор може одночасно виконувати дві програми — по одній на кожному ядрі. Проте через особливості архітектури одночасно на двох ядрах одного процесора можуть виконуватись лише однакові інструкції.

Під час виконання двох програм на процесорі спеціальний керівний пристрій оптимізує виконання так, щоб завершити виконання обох програм якомога раніше. Наприклад, програми "$ABB$" та "$ABC$" можна виконати на процесорі за $4$ такти: спочатку одночасно виконуються команди "$A$" обох програм на різних ядрах, потім одночасно команди "$B$", потім команда "$B$" з першої програми і, нарешті, "$C$" з другої. Аналогічно, програми "$CAB$" та "$BAB$" виконуються за $4$ такти.

Нещодавно спеціалісти компанії зібрали з $n$ процесорів суперкомп'ютер, на якому потрібно виконати $2n$ програм. Організація обчислень така, що кожен процесор повинен виконати рівно по дві програми з цього набору, по одній на кожному ядрі.

Вам необхідно спланувати виконання $2n$ програм на $n$ процесорах так, щоб час завершення виконання усіх програм був мінімальним.