配点 : 100 点
問題文
。请用 SAT 解以下谜题。
- 6*6 的格子会被给出。其中一些格子是黑格,其他为白格。
- 将一些白格变为黑格,使其满足以下条件。
- 白格的连通分量恰好存在 4 个,并且其大小均为 4 。
。下图示例题也可参考。
図1:例題
为了以后方便,给格子编号如下。
图2:方格编号
解答方法
您需要为了解开这个谜题提交如下的CNF。
- 逻辑变量仅使用 x_1, x_2, ..., x_{1000} 。
- 对于满足公式的真值分配,x_i (1 \leq i \leq 36) 表示谜题解答棋盘上的方格 i 的颜色。 当x_i 为真时的方格 i 是黑色的,如果为假则为白色。
判定方法
判定如下进行。
- 在提交的 CNF 中添加以下子句。
- 在测试用例的拼图初始盘面中,如果格子 i 被涂成黑色,(x_i) 就会被添加为子句。(通过此操作,x_i 必然为真。)
- 判断 CNF 的可满足性。如果不可满足,裁判结果是
WA成为。此外,如果此判定花费了 30 秒以上,如果IE变为。 - 可满足,则分配布尔值 1 进行查找,将各 i (1 \leq i \leq 36) , 当我输入x_i 为真时的方格 i 填成黑格,若为假则填成白格。
- 判断得到的棋盘是否作为谜题的解答是正确的。若正确则裁判结果为
AC,若不正确则WA变为。
测试用例是 10 有案例,如果全部答对 AC 。
对于
这个 gist 已经上传了裁判的源代码,请用于调试等。
入力
没有针对此问题提供任何输入。 打印
出力
i 线 i 输出第 n 节的信息,并在最后一行 0 输出。 各节的输出方法参考 minisat 。 对于
例如 第 (x_1 \lor x_2) \land (\lnot x_1 \lor x_2 \lor \lnot x_3) 这种 CNF 的情况,可以按以下方式输出。
1 2 0 -1 2 -3 0 0
注意点
注意以下几点。
- 字面量只能 x_1 减去 x_{1000} 使用到这里为止
- 不能插入空节。(0 仅会输出()在行中,并会被判定为输出结束)