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相同。 您可以仅提交预先计算出的输出,例如手动计算的输出。
工具
- 网页版可视化工具/输入生成器
- 本地执行版本可视化器/输入生成器:使用,Rust 语言 请为准备编译环境。
入力例 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