← 返回题目列表

AtCoder · xmascon17_i

I. SAT 谜题

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

配点 : 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 仅会输出()在行中,并会被判定为输出结束)