Solved by 110 users: ...
UserDateAttemptTimeCMSC
RAVEman`06 sep 2009`C++300.89315
RAVEman`06 sep 2009`C++400.26328
RAVEman`01 jun 2010`C++2700.02373
RAVEman`01 jun 2010`C++2800.02373
fetetriste`19 apr 2008`C++500.05379
RAVEman`01 jun 2010`C++2300.02394
Korduban`01 apr 2008`C++300.02397
Vladislav_Simonenko`19 apr 2006`C++100.10400
fetetriste`19 apr 2008`C++400.05404
Korduban`01 apr 2008`C++400.02413
ZhanibekDATBAEV`26 may 2010`C++300.02416
tomek`09 may 2006`C++301.64419
doriath`06 dec 2006`C++401.70420
WsemirZ`29 may 2008`C++1100.02437
WsemirZ`29 may 2008`C++1000.02443
DAV`27 jun 2009`C++1100.03444
MasterYoda`28 jun 2009`C++1300.04444
MasterYoda`28 jun 2009`C++1500.04444
DAV`27 jun 2009`C++1300.03447
 C++ 84 FPC 13 Kylix 9 Java 4
` >  >  >  >  >  >  >  >  >  > `

## SAT-2

Time limit = 2 second(s)

The SAT-3 problem is known to be NP-complete. The SAT-2 problem can be solved in polynomial time. Do it.

Input is boolean function of N boolean variables given in the form:

and and ..

where is one term or binary OR of two terms. Term is a variable or its negation.

Example: (X1 or X2) and (X3 or not(X4)) and X5

Your program should find out if there is values of boolean variables which make expression true.

Input. The first line contains N and M (N < 1000, M < 10000).

Boolean variables are identified by their indexes 1,2, .., N. Then descriptions of M or-expressions follow. Each or-expression is one or two indexes of boolean variables. If index prepended by sign '-', then corresponding term is negation of the variable.

Example. Expression

```  (X1 or X2) and
(X3 or not X4) and
X5
```
will be given in input as
```5 3
1 2 0
3 -4 0
5 0
```

Output. Output line with 'Yes', if such set of boolean values exists. and 'No' otherwise. If 'Yes', the next line should contain indexes of variables, which should be set to TRUE (others should be set to FALSE) to make expression TRUE.

 Input#1```6 3 1 2 0 3 -4 0 5 0 ``` Output#1```Yes 1 5 0 ```
 Input#2```16 3 1 -2 0 2 -3 0 3 -1 0 ``` Output#2```Yes 0 ```
 Input#3```4 6 1 -2 0 1 -3 0 2 3 0 -1 -4 0 4 -2 0 4 -3 0 ``` Output#3```No ```

Author:
Tests and descriptions by Artem Voroztsov

<PREV | Problem set | Search related messages | NEXT>

 © acm.mipt DevGroupThe page was generated in 190ms