说明

A、B、C三个问题只有测试用例数量和输入生成方法不同。请参考A问题的公共部分。

测试用例数量

50个

输入生成方法

固定 $K=10$，$B=20$。印记的坐标是从已放置印记中选取最小的曼哈顿距离大于等于10的坐标中均匀随机选择的。其中，第一个印记在上边界 ($i_1=0$)，第二个印记在左边界 ($j_2=0$)，第三个印记在下边界 ($i_3=N-1$)，第四个印记在右边界 ($j_4=N-1$) 中进行均匀随机选择。

每个多米诺骨牌构成如下。我们将构成多米诺骨牌的每个正方形称为块。第一个多米诺骨牌由一个块组成，成本为 $C_1=50$。第 $b$ ($2 \leq b \leq B$) 个多米诺骨牌由 $2+b$ 个块组成，成本为 $C_b=\mathrm{round}(50\sqrt{2+b})$，从一个块的多米诺骨牌开始，重复以下扩展操作 $1+b$ 次生成：

1. 随机选择扩展的方向，可以选择上、下、左、右四个方向中的一个。
2. 从该方向上最靠近边缘的块中均匀随机选择一个，通过将其相邻的正方形包含在多米诺骨牌中来扩展一个块。

工具

• Web版可视化器和输入生成器
• 本地执行版可视化器和输入生成器: 请准备Rust语言的编译环境以使用。

输入示例1

50 10 20
0 25
1 0
49 21
49 49
0 43
41 9
26 6
12 32
38 33
13 4
1 1 50
#
2 3 100
###
#..
2 4 112
#...
####
5 2 122
.#
.#
##
#.
#.
3 5 132
..###
###..
.#...
2 7 141
###....
..#####
7 3 150
..#
..#
..#
..#
..#
..#
###
5 6 158
...#..
..####
..#...
###...
.#....
7 5 166
...#.
...#.
...#.
####.
...##
...#.
...#.
5 8 173
...#....
...#....
########
.....#..
.....#..
9 5 180
..#..
..#..
..#..
..#..
#####
..#..
..#..
..#..
..#..
8 7 187
..#....
..#....
..#....
..#....
#######
.#.....
.#.....
.#.....
8 8 194
.......#
.....###
######..
...#....
...#....
...#....
...#....
...#....
5 12 200
.......#....
.......#####
########....
.....#......
.....#......
12 6 206
...#..
...#..
...#..
...#..
...#..
...###
####..
...#..
...#..
...#..
...#..
...#..
10 9 212
.......#.
.......#.
.......#.
#########
.......#.
.......#.
.......#.
.......#.
.......#.
.......#.
14 6 218
...#..
...#..
...#..
...#..
...#..
######
...#..
...#..
...#..
...#..
...#..
...#..
...#..
...#..
9 12 224
.....#......
.....#......
.....#......
.....#......
.....#......
.....#......
######......
.....##.....
......######
9 13 229
........#....
........#....
........#....
........#....
#############
.......#.....
.......#.....
.......#.....
.......#.....
10 13 235
.....#.......
.....#.......
.....#.......
#######......
......#......
......#######
......#......
......#......
......#......
......#......

输出示例1

164
1 26 6
1 25 6
1 24 6
1 23 6
1 22 6
1 21 6
1 20 6
1 19 6
1 18 6
1 17 6
1 16 6
1 15 6
1 14 6
1 13 6
1 13 5
1 13 4
1 1 0
1 1 1
1 1 2
1 1 3
1 1 4
1 2 4
1 3 4
1 4 4
1 5 4
1 6 4
1 7 4
1 8 4
1 9 4
1 10 4
1 11 4
1 12 4
1 0 25
1 0 26
1 0 27
1 0 28
1 0 29
1 0 30
1 0 31
1 0 32
1 0 33
1 0 34
1 0 35
1 0 36
1 0 37
1 0 38
1 0 39
1 0 40
1 0 41
1 0 42
1 0 43
1 41 9
1 40 9
1 39 9
1 38 9
1 37 9
1 36 9
1 35 9
1 34 9
1 33 9
1 32 9
1 31 9
1 30 9
1 29 9
1 28 9
1 27 9
1 26 9
1 26 8
1 26 7
1 1 32
1 2 32
1 3 32
1 4 32
1 5 32
1 6 32
1 7 32
1 8 32
1 9 32
1 10 32
1 11 32
1 12 32
1 49 21
1 48 21
1 47 21
1 46 21
1 45 21
1 44 21
1 43 21
1 42 21
1 41 21
1 41 20
1 41 19
1 41 18
1 41 17
1 41 16
1 41