← 返回题目列表

AtCoder · future_fif_digital_days_a

A. 多联骨牌连接 A

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

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

問題文

N\times N 方板和 B 多骨牌有不同类型。 左上角方块的坐标 (0, 0) 然后从那里下去。 i 向右方格 j 你移动到的方块的坐标 (i, j) 。 在初始状态下,所有方格都是不可通行的,但是当将多联骨牌放在棋盘上时,其上方的空间就变得可以通行。 在板上 K 方块已标记,我想通过放置多联骨牌连接所有标记的方块。

例如上图中,左上标记和右上标记是相连的,但下面的标记是不相连的。

您可以放置​​任意数量的相同类型的多联骨牌,但不能旋转它们或将它们放置在从板上突出的位置。 此外,不可能将两个或多个多联骨牌放在一个方格上。 每种多联骨牌的类型 每 b 的成本 C_b 是固定的,并且多联骨牌 当放置 b 的 m_b 件时,总成本为 \sum_{b=1}^B C_b m_b 变为。 我希望所有标记的方块都以尽可能低的总成本连接起来。

得点

总成本 S 您将获得\mathrm{round}(10^8 / S) 分数。 如果输出不正确(标记的方块未连接、多联骨牌从板上突出或重叠),被确定。 在一个或多个测试用例中 如果做出以外的判断,则提交分数将为0分。 最终排名以比赛时间内获得的最高分决定,比赛结束后不再进行系统测试。 如果多名参赛者获得相同分数,则第一个获得该分数的提交作品排名较高。


入力

输入是按以下格式从标准输入给出的。

N K B
i_1 j_1
\vdots
i_K j_K
n_1 m_1 C_1
s^1_{1,1} \ldots s^1_{1,m_1}
\vdots
s^1_{n_1,1} \ldots s^1_{n_1,m_1}
\vdots
n_B m_B C_B
s^B_{1,1} \ldots s^B_{1,m_B}
\vdots
s^B_{n_B,1} \ldots s^B_{n_B,m_B}

第一行是一个整数,代表棋盘的垂直和水平尺寸。 N,标记的方块总数 K,多联骨牌类型数量 给出了 B 。在所有测试用例中 它固定为 N=50 。

继续 K 行给出了有关标记方块的信息,并且 p 行是 第 p 个标记的坐标是 (i_p, j_p) ,0\leq i_p\leq N-1, 0\leq j_p\leq N-1 满意。 标记的坐标都不同。

最后 B 一一给出了每种类型多联骨牌的信息。 表示围绕第

  • n_b 和 m_b 是 b 个多联骨牌的最小矩形(边界框)的垂​​直和水平尺寸。 一个正整数,表示放置一个n_1=m_1=1 有保证。
  • C_b 是 b 多联骨牌所需的成本。 从上面看第
  • s^b_{i,j} 是 b 个多骨牌的边界框 i 正方形,从左起 j 代表网格的信息,# 属于多联骨牌,. 表示它不属于多骨牌。
  • 每个多骨牌都保证已连接。

出力

第一行中使用的多联骨牌总数,格式如下 m ,继续 m 行包含一个表示所使用的多联骨牌类型的整数。 b_i (1\leq b_i\leq B) 和边界框的左上角坐标 逐行输出 (x_i, y_i) (0\leq x_i\leq N-n_{b_i}, 0\leq y_i\leq N-m_{b_i})。

m
b_1 x_1 y_1
\vdots
b_m x_m y_m

测试用例数量

1 個

入力生成方法

问题A的测试用例数量为1,与输入示例1相同。 您可以仅提交预先计算出的输出,例如手动计算的输出。


入力例 1

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

出力例 1

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