[信息与未来 2018] 棋盘游戏

Luogu
IDLGB3740
Time1000ms
Memory128MB
DifficultyP3
搜索贪心2018江苏进制信息与未来
给定一个十进制数 $x$,将它转换为二进制字符串并在高位填 $0$ 以补足 $16$ 位,就得到了 一个长度为 $16$ 的 $01$ 字符串,我们用这个字符串表示 $4 × 4$ 的棋盘,按从左到右、从上到下的顺序将 $0$(白子)、$1$(黑子)放入棋盘。 例如,$(447)_{10} = (0000 0001 1011 1111)_2$,按顺序填入棋盘($0$ 白子、$1$ 黑子),得到如下棋盘(左边棋盘): ![](https://cdn.luogu.com.cn/upload/image_hosting/vyma7pie.png) 我们现在可以交换棋盘中**相邻**(共享一条边的两个格子相邻,因此一个格子至多有 $4$ 个相邻的格子)的黑色和白色棋子。从左图的棋盘变为全部白子在上、全部黑子在下(右边棋盘所示)的棋盘,至少需要 $3$ 步。 对于给定的棋盘(保证棋盘中恰好有 $8$ 个白子和 $8$ 个黑子),求把棋盘变为全部白子在上、全部黑子在下最少的交换步数。 ## Input 输入一行一个整数 $x$,为十进制表示下的棋盘。 ## Output 输出一行一个整数,最少需要交换的步数。 [samples] ## Note ### 样例解释 #### 样例 $1$ 参考上图,将 $(2, 4)$ 处的⿊⼦移动到 $(3, 2)$ 需要 $3$ 步。 #### 样例 $2$ 如下图所示,$(42405)_{10} =(1010 0101 1010 0101)_2$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/aie8kf0n.png) ### 数据规模 $50\%$ 的测试数据满足棋盘可以在 $6$ 次交换内变为白子在上、黑子在下。 所有数据保证 $0 ≤ x < 2^{16}$,且 $x$ 转换为二进制后恰好有 $8$ 个 $1$。 > 本题原始满分为 $20\text{pts}$。
Samples
Input #1
447
Output #1
3
Input #2
42405
Output #2
8
API Response (JSON)
{
  "problem": {
    "name": "[信息与未来 2018] 棋盘游戏",
    "description": {
      "content": "给定一个十进制数 $x$,将它转换为二进制字符串并在高位填 $0$ 以补足 $16$ 位,就得到了 一个长度为 $16$ 的 $01$ 字符串,我们用这个字符串表示 $4 × 4$ 的棋盘,按从左到右、从上到下的顺序将 $0$(白子)、$1$(黑子)放入棋盘。 例如,$(447)_{10} = (0000 0001 1011 1111)_2$,按顺序填入棋盘($0$ 白子、$1$ 黑子),得到如",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3740"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个十进制数 $x$,将它转换为二进制字符串并在高位填 $0$ 以补足 $16$ 位,就得到了\n一个长度为 $16$ 的 $01$ 字符串,我们用这个字符串表示 $4 × 4$ 的棋盘,按从左到右、从上到下的顺序将 $0$(白子)、$1$(黑子)放入棋盘。\n\n例如,$(447)_{10} = (0000 0001 1011 1111)_2$,按顺序填入棋盘($0$ 白子、$1$ 黑子),得到如...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments