시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB830292306.329%

문제

3-SAT은 N개의 불리언 변수 \(x_1, x_2, ..., x_n\)가 있을 때, 3-CNF 식을 true로 만들기위해 \(x_i\)를 어떤 값으로 정해야하는지를 구하는 문제이다.

3-CNF식은 \( \left( x \lor y  \lor \lnot z\right) \land \left( x \lor \lnot y \lor z \right) \land \left( \lnot w \lor x \lor \lnot z \right) \land \left( x \lor z \lor y \right) \) 와 같은 형태이다. 여기서 괄호로 묶인 식을 절(clause)라고 하는데, 절은 3개의 변수를 \(\lor\)한 것으로 이루어져 있다. \(\lor\)는 OR, \(\land\)는 AND, \(\lnot\)은 NOT을 나타낸다.

변수의 개수 N과 절의 개수 M, 그리고 식 \(f\)가 주어졌을 때, 식 \(f\)를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하시오.

예를 들어, N = 3, M = 4이고, \(f =  \left( \lnot x_1 \lor x_2 \lor x_3 \right) \land \left( \lnot x_1 \lor \lnot x_2 \lor x_3 \right) \land \left( x_1 \lor \lnot x_2 \lor x_3 \right) \land \left( x_3 \lor \lnot x_2 \lor \lnot x_1 \right) \) 인 경우에 \(x_1\)을 false, \(x_2\)을 false, \(x_3\)를 true로 정하면 식 \(f\)를 true로 만들 수 있다. 하지만, N = 1, M = 2이고, \(f = \left( x_1 \lor x_1 \lor x_1 \right) \land \left( \lnot x_1 \lor \lnot x_1 \lor \lnot x_1 \right) \)인 경우에는 \(x_1\)에 어떤 값을 넣어도 식 f를 true로 만들 수 없다.

입력

첫째 줄에 변수의 개수 N (1 ≤ N ≤ 1,000)과 절의 개수 M (1 ≤ M ≤ 10,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 세 정수 i, j, k (1 ≤ |i|, |j|, |k| ≤ N)로 이루어져 있으며, i, j, k가 양수인 경우에는 각각 \(x_i\), \(x_j\), \(x_k\)를 나타내고, 음수인 경우에는 \(\lnot x_{-i}\), \(\lnot x_{-j}\), \(\lnot x_{-k}\)를 나타낸다.

출력

첫째 줄에 식 \(f\)를 true로 만들 수 있으면 1을, 없으면 0을 출력한다.

\(f\)를 true로 만들 수 있는 경우에는 둘째 줄에 식 \(f\)를 true로 만드는 \(x_i\)의 값을 \(x_1\)부터 순서대로 출력한다. true는 1, false는 0으로 출력한다.

예제 입력 1

3 4
-1 2 3
-1 -2 3
1 -2 3
3 -2 -1

예제 출력 1

1
0 0 1

예제 입력 2

6 8
1 6 2
3 -4 5
2 -2 3
5 -1 4
-4 6 -2
1 -6 -3
2 -3 4
6 -4 -1

예제 출력 2

1
0 1 0 0 1 1

예제 입력 3

6 8
-1 6 2
-3 -4 5
2 -2 -3
5 -1 -4
-4 -6 -2
1 -6 -3
2 -3 4
6 -4 -1

예제 출력 3

1
0 1 0 0 1 0

예제 입력 4

1 2
1 1 1
-1 -1 -1

예제 출력 4

0

출처

채점 및 기타 정보

  • 100개 이상의 데이터를 맞아야 를 받는다.