← 返回题目列表

AtCoder · utpc2013_05

E. 二元布尔可满足性

中文机器翻译题面 查看原题

問題

背景

鳗鱼王国的王子喜欢CNF。每天,我都在努力寻找令人满意的解决方案。就连王子也厌倦了可满足性问题。于是王子决定请国王问他一个不寻常的问题。看来下一道题不仅需要逻辑表达式,还需要变量赋值。

課題

2-SAT(satisfiability) 表示子句的长度(最多) 以乘法标准形式2表示的逻辑表达式 ( 给定2-CNF),问题是通过适当地为每个变量分配真/假来确定逻辑表达式是否可满足。现在你是2-CNF 和对每个变量的真/假赋值。然而不幸的是,这种变量分配可能不是一个足够的解决方案。找出使赋值成为令人满意的解决方案所需的变量赋值的最少更改次数。然而,答案是 如果大于等于11或者逻辑公式不满足,则打印“TOO LARGE”。

配点

200

入力

输入按以下格式给出。

n m
cnf
a1a2...an

n 是变量的数量,m 表示子句的数量。 a1a2...an 表示变量赋值,ai=T 然后变量 i 分配正确且 这意味着ai=F 然后变量 i 的分配是错误的。2-CNF 由以下 BNF 给出。

  • “^”表示逻辑积,“v”表示逻辑和,“~”表示否定运算符。
  • 每个变量是 由 1,2,...,n-1,n 代表
<cnf> ::= <clause> | <clause>"^"<cnf>
<clause> ::= "("<literal>"v"<literal>")"
<literal> ::= <var> | "~"<var>
<var> ::= [1-9] | <var>[0-9]

制約

输入中的每个变量都满足以下约束。

  • 1 \leq n \leq 10000 (=104)
  • 1 \leq m \leq 100000 (=105)
  • BNF中<var>的值为 1 减去 n 是

出力

在一行上输出使赋值成为令人满意的解决方案所需的变量赋值更改的最小数量。然而,答案是11或者逻辑公式不满足,则打印“TOO LARGE”。

入力例1

4 2
(~1v2)^(3v~4)
TTFF

输入示例 1 的输出示例 路径

0

该作业已分配2-CNF 满意。

入力例2

3 4
(~1v~2)^(1v3)^(2v~1)^(~3v1)
FFT

输入示例 2 的输出示例

TOO LARGE

这个2-CNF 没有令人满意的解决方案。

入力例3

22 11
(1v2)^(3v4)^(5v6)^(7v8)^(9v10)^(11v12)^(13v14)^(15v16)^(17v18)^(19v20)^(21v22)
FFFFFFFFFFFFFFFFFFFFFF

输入示例 3 的输出示例

TOO LARGE

至少 如果不更改11变量的分配,则无法满足此 2-CNF。