Кільця та Руни#6978
Фродо увійшов до шахт Морії і натрапив на низку воріт. На кожних воротах написана давня загадка, що описує стан набору спеціальних кілець, які контролюють ці ворота. Вивчаючи загадку, Фродо може визначити, чи можна відкрити ворота, чи це просто пастка.
Загадки складаються з кількох рун. Дійсна руна містить рівно твердження про різні кільця. Кожне твердження в руні може бути істинним або хибним, залежно від стану (обертається чи не обертається) певного кільця в наборі кілець, що контролюють ворота. Загадка для конкретних воріт не обов'язково повинна використовувати всі можливі кільця, що містяться в наборі, який контролює ворота.
Щоб відкрити ворота, гобіти повинні прочитати загадку, а потім вирішити, які з кілець обертати, а які залишити в спокої. Коли вони правильно обертають кільця, вони вимовляють заклинання, і якщо вся загадка для воріт задовольняється, ворота відкриються. Щоб ворота відкрилися, кожна руна в загадці повинна мати принаймні одне твердження, яке є істинним.
Наприклад, розглянемо конкретну руну: . Ця руна буде істинною, якщо (кільце обертається) АБО (кільце НЕ обертається) АБО (кільце обертається). (ПРИМІТКА: вказує на кінець руни, і принаймні одне з тверджень у цій руні має бути істинним, щоб ця конкретна руна була істинною.) Якщо номер кільця в руні негативний (наприклад, ), це означає, що кільце має НЕ обертатися, щоб це конкретне твердження в руні було істинним. Якщо номер кільця позитивний (наприклад, ), це означає, що кільце МАЄ обертатися, щоб це твердження в руні було істинним. Конкретне кільце може з'являтися лише один раз у конкретній руні, однак кільце може використовуватися кілька разів у всій загадці, але не в одній руні!
Вхідні дані складатимуться з наступного:
Перша строка вхідних даних містить одне ціле число (де 1 \le g \le 30), яке позначає кількість воріт із загадками, які потрібно розшифрувати.
Перша строка для кожних воріт містить два цілі числа, (де 3 \le rings \le 22) та (де 1 \le runes \le 100), розділені пробілом. - це кількість кілець у контрольному наборі; кожне кільце пронумероване від до , і загадки не зобов'язані використовувати кожне можливе кільце. - це кількість рун, які мають бути задоволені набором кілець.
Наступні рядків описують окремі руни, які визначають відносини між кільцями для цих воріт. Кожна руна представлена одним рядком, що містить чотири числа: r_1, r_2, r_3 і , де кожне з цих чисел розділене пробілом. Перші три числа є -бітними цілими числами.
Кожні ворота містять рівно одну загадку (що складається з кількох рун), і ваш алгоритм повинен вивести рівно один рядок для кожних воріт. Якщо одна або більше рун у загадці містять помилки, виведіть лише помилку з найвищим пріоритетом для цієї загадки. Пріоритет помилок описаний нижче:
Якщо БУДЬ-ЯКА руна в загадці містить твердження про нульове кільце, наприклад, або , це найсерйозніша помилка в загадці, і вся загадка є недійсною. Виведіть "INVALID: NULL RING" як помилку з найвищим пріоритетом.
Якщо БУДЬ-ЯКА руна в загадці містить твердження або , де (r < -rings) або (r > rings), то це ДРУГА за серйозністю помилка в загадці, і тому виведіть "INVALID: RING MISSING". ПРИМІТКА: НЕ виводьте це повідомлення, якщо загадка містила НУЛЬОВЕ кільце!
Якщо БУДЬ-ЯКА окрема руна посилається на те саме кільце більше одного разу (наприклад, АБО ), це ТРЕТЯ за серйозністю помилка, тому виведіть "INVALID: RUNE CONTAINS A REPEATED RING". Знову ж таки, не виводьте це повідомлення, якщо десь у загадці сталася помилка з вищим пріоритетом.
Загадки можуть містити повторювані руни. Розглядайте всі ці повторювані руни як одну руну; оскільки вони ідентичні, якщо одна є істинною, всі повторювані руни будуть істинними.
Якщо існує конфігурація обертових/нерухомих кілець, яка задовольняє всі руни в загадці, виведіть "RUNES SATISFIED!"
Якщо немає можливої конфігурації обертових/нерухомих кілець, яка задовольняє всі руни, виведіть "RUNES UNSATISFIABLE! TRY ANOTHER GATE!"
Приклад 1