<ПРЕД Задача:
СЛЕД>
Задачу решили 110 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

SAT-2

Time limit = 2 секунд(ы)

Известно, что проблема SAT-3 NP-полная. Вам предлагается решить проблему SAT-2, которая полиноминально разрешима.

Дана булева функция N переменных, записанная как операция AND над несколькими простыми выражениями. Простое выражение есть оперция OR двух термов или один терм. Каждый терм есть булева переменная или её отрицание.

Пример логического выражения: (X1 or X2) and (X3 or not(X4)) and X5

Требуется написать программу, которая определяет, есть ли такие значения переменных, при которых данное на входе выражение становится истинным. Если такие значения есть, то ваша программа должна вывести один из подходящих наборов значений переменных.

Вход. В первой строке входа указаны число переменных N и число простых логических выражений M (N < 1000, M < 10000).

Далее идёт описание M простых логических выражений. Описание одного простого логического выражения представляет собой одно или два числа, равных номерам переменных. Перед номером переменной указывается знак минус, если соответствующая переменная взята с отрицанием. Описание простого логического выражения заканчивается нулём. Переменные нумеруются числами 1, 2, ... N.

Например, логическое выражение

  (X1 or X2) and
  (X3 or not X4) and
  X5
на входе будет описано как
5 3
1 2 0
3 -4 0
5 0

Выход.

Выведите в первой строчке 'Yes', если данное выражение может быть истинным, и 'No' — если нет. В первом случае в следующей строчке выведите также номера всех переменных, которым следует назначить значение 'истина', чтобы данное выражение было истинным (остальные считаются равными 'ложь').

Вход#1
6 3
1 2 0
3 -4 0
5 0

Выход#1
Yes
1 5 0

Вход#2
16 3
1 -2 0
2 -3 0
3 -1 0

Выход#2
Yes
0

Вход#3
4 6
1  -2 0
1  -3 0
2   3 0
-1 -4 0
4  -2 0
4  -3 0

Выход#3
No


Автор:
Классика, тесты и описание -- Ворожцов Артём.

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 3.209.10.183