luogu#P1745. [CERC2016] Lost Logic

[CERC2016] Lost Logic

题目描述

Gustav is reading about 2-satisfiability, a well known problem of assigning truth values to boolean variables in order to satisfy a list of constraints — simple logical formulas involving two variables each.

We are using nn variables x1,x2,,xnx_1, x_2, \cdots , x_n that can take on values 00 (false) and 11 (true). A constraint is a formula of the form aba\to b where both aa and bb are possibly negated variables. As usual, \to denotes logical implication: aba \to b is 00 only when aa is 11 and bb is 00. The negation of variable aa is denoted by !a!a.

Given an assignment of values to variables, we say that the constraint is satisfied if it evaluates to 11. Gustav has constructed a list of constraints and correctly concluded that there are exactly three different assignments of values to variables that satisfy all the constraints. Gustav has wrote down all three assignments but has, unfortunately, lost the list of constraints. Given three assignments of nn values to variables, find any list consisting of at most 500500 constrains such that the three given assignments are the only assignments that satisfy all the constraints.

输入格式

The first line contains an integer n(2n50)n (2 \leq n \leq 50) — the number of variables. Three lines follow, each describing one assignment. The kk-th line contains nn space-separated integers v1k,v2k,,vnkv_1^k,v_2^k,\cdots,v_n^k, where each vikv_i^k is either 00 or 11 and denotes the value of the variable xix_i in the kk-th assignment. All three assignments will be different.

输出格式

If there is no solution output a single line containing the integer 1−1. Otherwise, the first line should contain an integer mm where 1m5001 \leq m \leq 500 — the number of constraints in your solution. The kk-th of the following mm lines should contain the kk-th constraint. Each constraint should be a string constructed according to the following rules:

  • A variable is a string of the form “xi\texttt{x}i” where ii is an integer between 11 and nn inclusive written without leading zeros.
  • A literal is a string consisting of a variable possibly preceded by the “!\texttt{!}” character.
  • A constraint is a string of the form “a -> ba\texttt{ -> }b” where both aa and bb are literals. The implication sign consists of the “minus” character and the “greater-than” character and there is a single space character both before and after the implication sign.

题目大意

给定 33 组随机布尔变量 vi,1,...,vi,n(1i3)v_{i,1},...,v_{i,n}(1\leq i\leq 3),每组均为 nn 个。你需要构造关于布尔变量 x1,...,xnx_1,...,x_n 的若干组条件,使得满足全部条件的布尔变量赋值有且仅有 (vi,1,...,vi,n)(1i3)(v_{i,1},...,v_{i,n})(1\leq i\leq 3)33 组。

由于机器限制,你所构造每组条件的形式均应为:ABA\rightarrow B。这组条件的限制了:当 AA11BB 一定为 11。其中,A,BA,B 可能形如:

  • xix_i:表示第 ii 个变量的值。
  • !xi!x_i:表示第 ii 个变量取反后的值。

例如,如果你构造了 x1x2x_1\rightarrow x_2,那么表示你规定 x1=1x_1=1 时必有 x2=1x_2=1;如果你构造了 !x1x2!x_1\rightarrow x_2,那么你规定了 x1=0x_1=0 时必有 x2=1x_2=1。你需要找到一种使用不超过 500500 组条件来满足题意的方法,或者判定这样的条件组合不可能存在。如果有多组解,输出任意一组均可。

数据保证 $2\leq n\leq 50,v_{i,j}\in\{0,1\}(1\leq i\leq 3,1\leq j\leq n)$。

3
0 0 0
0 1 0
1 0 0
3
x1 -> !x2
x3 -> x1
x3 -> x2
4
0 0 1 0
1 0 0 0
1 0 1 1
-1