Шаріф Суперкомп'ютер

SSC — це суперкомп'ютер, розроблений у Шаріфському університеті з $2$ контролерами та $n$ робочими процесорами. Він може запускати програмне забезпечення паралельно: один із контролерів завантажує програму на робочі процесори так, щоб використання пам'яті й процесора між ними було збалансованим, тоді як інший контролер слугує для моніторингу системи.

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

Є два типи кабелів: сині кабелі, які можуть передавати до $100$ Мегабіт за секунду, і червоні кабелі, що можуть передавати до $1$ Гігабіта за секунду. Кожна пара робочих процесорів буде з'єднана одним синім кабелем. Через більший обсяг взаємодії на контролерах, два контролери з'єднуються одним червоним кабелем, а також кожен контролер з'єднується з кожним робочим ще одним червоним кабелем.

Отже, SSC складається з n + 2 материнських плат, кожна з яких містить рівно один процесор, необхідну пам'ять, а також n + 1 однакових мережевих роз'ємів, встановлених горизонтальним рядом. Материнські плати розміщують у вертикальному шафовому корпусі, кожну на окремій горизонтальній полиці. Тому кожній платі відповідає певна висота у стійці.

Охолоджувальна система змусила нас розташувати обидві материнські плати контролерів на найнижчій та найвищій полицях шафи. Вважається, що контролер унизу має висоту $0$, а висоти інших материнських плат — це цілі числа, більші за $0$. Ви, як комп'ютерний інженер, повинні виконати фінальне складання SSC. Вам надано порожню шафу та готові плати, і ваше завдання — визначити, чи можете ви розташувати плати у шафі так, щоб усе відповідало обмеженням і довжинам кабелів.

Є рівно 2n + 1 червоний кабель із заданими розмірами. Проте сині кабелі доступні у $m$ різних розмірах, і їх у кожному розмірі необмежена кількість. Ви прагнете, щоб кабелі між процесорами були охайними та короткими, тому бажаєте встановити материнські плати на таких висотах, щоб розмір кабелю між будь-якою парою плат був точно рівний різниці висот цих плат.