[Codeforces 1503B] 3-Coloring

[Wizmann]

题意

Problem

交互式问题。

Alice和Bob玩一个游戏。Bob需要在一个N * N的矩阵里填3种颜色（记作1，2，3）。

Alice在每一轮的开始，会选出一个[1, 2, 3]中的一个数字k。Bob会选择一个颜色c，使得c != k，任选一个位置填入矩阵。要求矩阵相邻（上下左右）的格子里不能有相同的颜色。

问Bob每一轮应该采用什么策略。

解法

如果只有两种颜色的话，最直接的思路是采用棋盘格的布局。其限制在于单一一种颜色不能超过棋盘格总数的一半。

对于三种颜色，我们可以强制使用一种颜色（例如1）填充奇数块（白块），用一种颜色（例如2）填充偶数块（黑色），直到奇偶块有一种填满。

如果白块已经填满，我们需要考虑以下几种情况：

1. Alice给出数字1或3，Bob使用数字2填充黑块
2. Alice给出数字2，Bob使用数字3填充黑块

换句话说，用1白块，用2和3填充黑块。所以不会有相邻的同色块。

如果黑块已经填满，则方法类似。

Code