18639번 - Three Vectors 스페셜 저지다국어

You are given three distinct binary vectors of length n. Find any 2-CNF formula which satisfies the following conditions:

• The formula is true on these vectors;
• The number of vectors on which the formula is true is minimal possible;
• The formula is not too long.

Recall that a 2-CNF formula is a propositional formula of n boolean variables v₁, . . . , v_n which looks like

C₁ ∧ C₂ ∧ . . . ∧ C_m,

where each clause C_i is represented as a disjunction ±x_i1 ∨ ±x_i2 of two literals (by literal, we mean any variable or its negation). Here, x_ij ∈ {v₁, . . . , v_n} is one of the variables, and −x_ij is its negation: true becomes false, and false becomes true. We say that the formula f is true on a binary vector v if f(v₁, v₂, . . . , v_n) = 1.

If there are several valid formulas, you are allowed to output any one of them.

The first line of input contains a single integer n which denotes the length of the three vectors (2 ≤ n ≤ 10⁵). The i-th of the following three lines contains a binary string of length n denoting the i-th binary vector.

No two vectors coincide.

On the first line, print a single integer m (0 ≤ m ≤ 2 · 10⁵). Then output m lines, i-th of them containing two integers a_i and b_i (1 ≤ |a_i|, |b_i| ≤ n), denoting that the i-th clause is a conjunction of two literals: the first is v_ai if a_i > 0 and −v_|ai| otherwise, and the second is, similarly, v_bi if b_i > 0 and −v_|bi| otherwise. If your formula is empty (that is, m = 0), it is considered to be true for every possible input vector of size n.

Please note that, if you use too many clauses, your answer will be considered incorrect.