Рабочее место участника

…И обзавелись свободные народы Среднеземья магическими Кольцами: Эльфы – тремя, Гномы – семью и Люди – девятью. Но жизнь показала, что лучше бы они этого не делали, ибо Саурон устроил свою раздачу ювелирных изделий вовсе не из благотворительных соображений…

Благодаря профессору Толкину и режиссёру Джексону, эта история в настоящее время довольно широко известна. Немногие, однако, знают, что за действиями Саурона стоял вполне определённый математический расчёт. Попробуем проследить за ним, введя предварительно одну необходимую функцию. Положим . Если `i=j=1`, то эта функция `G_11(a,b)` даёт среднее геометрическое чисел `a,b`; функции же `G_12(a,b)` и `G_21(a,b)` – это что-то вроде "обобщённого среднегеометрического" с приоритетом первого или второго числа.

Каждому народу был изначально присущ определённый магический потенциал, который можно оценить целым числом от 1 до 5. По книге получается, что самым высоким (5) он был у Эльфов, а самым низким (1) – у Людей. Гномы магией пользовались лишь в примитивных строительных и ремесленных целях, так что их магический потенциал можно оценить двойкой: повыше, чем у Людей, но много ниже эльфийского. Кольца приумножили эти магические потенциалы своей кратностью, так что с учётом их влияния эльфийский потенциал стал равен 15, гномий 14, а человеческий 9.

Далее Саурон озаботился тем, чтобы народы не вздумали воспользоваться магией Колец для взаимного геноцида: все эти народы он рассматривал, как своих будущих подданных, и ему нужен был пресловутый "худой мир паче доброй войны".

Как известно из военной науки, для обеспечения успеха нападающая сторона должна иметь трёхкратное преимущество. Вроде бы тут всё было в порядке: после раздачи Колец никто ни перед кем такого преимущества не имел (и даже самое большое преимущество Эльфов над Людьми было менее чем двукратным).

Однако нельзя было исключать возможность союза двух народов против третьего. Саурон оценил, как разные народы относятся одни к другим, и по той же пятибалльной шкале получил следующее. Эльфы с Гномами одинаково терпеть не могли друг друга, так что их взаимные чувства оцениваются единицей. Люди с Гномами поддерживали нейтральные отношения: не было особой дружбы, но и обид не было; здесь можно поставить троечку. Самое же интересное было в отношениях Людей с Эльфами. Эльфы относились к Людям: ну, получше, чем к Гномам, но в целом весьма презрительно. На двоечку. Люди же перед Эльфами прямо-таки благоговели (Перворожденные и всё такое) – пятёрка и никак иначе.

Проведя исследования, Саурон вывел закон сложения магических потенциалов при союзе двух народов. Оказалось, что здесь играет роль ещё один фактор: кто именно был инициатором союза. Если отношение "народа-инициатора" к "народу-последователю" выражается числом `a`, а отношение "последователя" к "инициатору" числом `b`, то магический потенциал союза равен сумме магических потенциалов двух союзников, умноженному на коэффициент `G_21(a,b)`. (Так, например, союз Эльфов и Людей, инициированный Эльфами, имел бы магический потенциал, равный .) Если же союз двух народов обращается против третьего, то потенциал союза ослабляется: его необходимо разделить на сумму средних геометрических взаимоотношений союзника с объектом агрессии. (Обратившись против Гномов, союз Людей и Эльфов ослабился бы в `G_11(1,1)+G_11(3,3)=4` раза, так что его потенциал составил бы 88.4/4=22.1, чего против гномьих 14 явно недостаточно.)

Просчитав аналогичным образом остальные возможные союзы, Саурон убедился, что ни у кого не возникнет искушения устроить в Среднеземье геноцид и приступил к выполнению своего плана. Как мы знаем, у него даже почти получилось – если бы не мерз-з-ские хоббит-ц-сы… (Говорят, ради любопытства Чёрный властелин пытался построить магико-математическую модель и для более сложных союзов, но у него не хватило то ли познаний, то ли времени.)

Необходимо разработать программу, которая по описанию магической и политической ситуации находит все возможные конфликты "один на один" и "двое на одного" с гарантированной победой.

В первой строке файла число народов `3\ ≤\ n\ ≤\ 100`.

Во второй строке файла магические потенциалы народов `p_i` (`1\ ≤\ p_i\ ≤\ 5`).

В третьей строке файла число Колец, доставшихся народам `k_i` (`1\ ≤\ k_i\ ≤\ 20`).

В каждой из последующих `n` строк (одна на каждый народ) по (`n-1`) числу: отношения прочих народов к данному, перечисленные по порядку. Каждое отношение лежит в диапазоне от 1 до 5.

Список конфликтов "один на один" и "двое на одного" в лексикографическом порядке через пробел. Конфликты "один на один" должны выдаваться словами типа "1-5" (первый народ нападает на пятый), "двое на одного" – словами типа "1+2-4" (первый народ инициирует союз со вторым и нападает на четвёртый). В случае невозможности конфликтов выходной файл должен содержать слово "NO".

3
5 2 1
3 7 9
1 5
1 3
2 3

NO

3
5 2 1
10 7 9
1 1
1 1
1 1

1+2-3
1-2
1-3
2+1-3