← 返回题目列表

AtCoder · future_fif_digital_days_open_b

B. 未来FIF数字日开放赛B

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

A、B、C 这三个问题仅在测试用例的数量和生成输入的方法上有所不同。通用部分请参考问题A。

测试用例数量 用

50 個

入力生成方法

K=10、B=20 修复。 通过从与已放置的标记的最小曼哈顿距离为10或更大的坐标中均匀地随机选择坐标来生成标记的坐标。 但是,第一个标记位于顶部 (i_1=0),第二个标记位于左边缘(j_2=0),第三个标记是底部边缘(i_3=N-1),第四个标记位于右边缘(j_4=N-1)并随机统一选择。

每个多联骨牌的生成方式如下。 组成多联骨牌的每个正方形块 我们称之为。 第一个 Polyomyo 由 1 个区块和成本组成C_1=50。 b (2\leq b\leq B)第一个多联骨牌是 2+b 由块组成,成本为 C_b=\mathrm{round}(50\sqrt{2+b}) 从一块多联骨牌开始并执行以下扩展操作: 通过重复 1+b 次生成。

  1. 从四个方向(上、下、左、右)中统一随机选择扩展方向。
  2. 从该方向末端的块中均匀随机选择,并通过将该方向上的相邻方块包含到多联骨牌中来扩展一个块。

入力例 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 15
1 41 14
1 41 13
1 41 12
1 41 11
1 41 10
1 40 21
1 39 21
1 38 21
1 38 22
1 38 23
1 38 24
1 38 25
1 38 26
1 38 27
1 38 28
1 38 29
1 38 30
1 38 31
1 38 32
1 38 33
1 0 24
1 0 23
1 0 22
1 0 21
1 0 20
1 0 19
1 0 18
1 0 17
1 0 16
1 0 15
1 0 14
1 0 13
1 0 12
1 0 11
1 0 10
1 0 9
1 0 8
1 0 7
1 0 6
1 0 5
1 0 4
1 49 49
1 48 49
1 47 49
1 46 49
1 45 49
1 44 49
1 43 49
1 42 49
1 41 49
1 40 49
1 39 49
1 38 49
1 38 48
1 38 47
1 38 46
1 38 45
1 38 44
1 38 43
1 38 42
1 38 41
1 38 40
1 38 39
1 38 38
1 38 37
1 38 36
1 38 35
1 38 34