[信息与未来 2019] 方格覆盖

Luogu

IDLGB3755

Time1000ms

Memory128MB

DifficultyP3

模拟贪心2019江苏Special Judge构造信息与未来

给定一个 $n\times n$ 的矩形，其中从左上角开始，对角线上连续的 $k$ 个格子中有障碍物。你可以把若干 $1\times2$ 的小矩形放置到该大矩形中，要求是放置的两个小矩形不能占据相同的格子，且不能碰到障碍物。例如下图是 $n=4,k=2$ 的例子，我们放置了 $6$ 个 $1\times2$ 的小矩形。 ![](https://cdn.luogu.com.cn/upload/image_hosting/ifmknyb8.png) 给定 $n,k$，请你输出一个方案，使得放置的 $1\times2$ 小矩形尽可能多。可以证明，$n=4,k=2$ 时，至多只能放置 $6$ 个小矩形。 ## Input 输入一行两个用空格分隔的正整数 $n,k$，表示矩形的大小和障碍物的数量。 ## Output 输出 $n$ 行，每行 $n$ 个整数（用任意数量的空格分隔）。放置的小矩形分别用 $1,2,\cdots$ 编号。不放置小矩形的格子输出 $0$。如有多种最优方案（放置最多数量的小矩形），输出任意一种即可。 [samples] ## Note 对于 $50\%$ 的测试数据，有 $1\le k\le n\le10$。对于 $100\%$ 的测试数据，有 $1\le k\le n\le50$。 > 本题原始满分为 $20\text{pts}$。

Samples

Input #1

4 2

Output #1

Input #2

5 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[信息与未来 2019] 方格覆盖",
    "description": {
      "content": "给定一个 $n\\times n$ 的矩形，其中从左上角开始，对角线上连续的 $k$ 个格子中有障碍物。你可以把若干 $1\\times2$ 的小矩形放置到该大矩形中，要求是放置的两个小矩形不能占据相同的格子，且不能碰到障碍物。例如下图是 $n=4,k=2$ 的例子，我们放置了 $6$ 个 $1\\times2$ 的小矩形。 ![](https://cdn.luogu.com.cn/upload/im",
      "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": "LGB3755"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 $n\\times n$ 的矩形，其中从左上角开始，对角线上连续的 $k$ 个格子中有障碍物。你可以把若干 $1\\times2$ 的小矩形放置到该大矩形中，要求是放置的两个小矩形不能占据相同的格子，且不能碰到障碍物。例如下图是 $n=4,k=2$ 的例子，我们放置了 $6$ 个 $1\\times2$ 的小矩形。\n\n![](https://cdn.luogu.com.cn/upload/im...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments