背景
*这个“背景部分写的句子与问题关系不大。问题文本是“ 它从問題文部分开始。
20XX年,RCO量子服务器机房 ──── 大量RCO的量子计算机排列在这里。
RCO广告技术部门于2016年进入量子计算,2017年通过在实际量子计算机上运行机器学习程序并举办量子退火国际会议获得动力,此时已成为一家专门研究量子计算机的公司。
员工
RCO多年的研究揭示量子计算机具有以下特性:
- 量子计算机是 K 通过连接设备,您可以展示其强大功能。 K 如果多于或少于单位数,则不起作用。这连接了 K 支架称为“件”。
- 包含在一个部件中的量子计算机不能包含在另一个部件中。
- 一块的功率等于该块内每台量子计算机的能力的乘积。
该服务器机房有 H 行 W 在列网格中 H \times W 量子计算机一字排开,员工 X 的工作是决定连接哪台量子计算机。量子计算机只能连接到彼此相邻的相邻量子计算机。当后续连接的量子计算机可以到达一台量子计算机时,这些量子计算机就可以说是连接的。
员工X想要通过适当地创建棋子来最大化所有棋子的力量总和,但自从他失去了编程工作后,他也失去了编程能力!所以,你,他的密友,决定为他编写这个程序。
問題文
相同大小的方形单元格 H 行 W 我有一个矩形的列网格。1 \leq i \leq H, 1 \leq j \leq W 的整数
选择 i 和
按字典顺序比较 j ,
当我输入 i 行 j 位于列中的正方形的坐标 (i,\ j) 。在每个方格内
如果写入任何字符 0 以上 9 写入以下整数之一。
在此网格上创建一些片段。和平只是 网格上由 K 方块组成的区域。一块内的方块必须相互连接。当方块相连时,意味着棋子中的所有成对的方块都可以通过沿着棋子内垂直和水平连接的方块相互到达。
您可以创建尽可能多的棋子,但用于创建棋子的方块不能用于创建另一棋子。
每首曲子都有一个分数。写在该作品包含的正方形上 K 整数的乘积就是该片段的分数。最大化所有棋子的总分。
制約
- H = 50
- W = 50
- K = 8
- 在每个测试用例中,每个方格中写入的整数被独立地写入每个方格的均匀随机数。 0 以上 9 将生成包含以下整数的值。
入力
输入是按以下格式从标准输入给出的。
H W K s_1 s_2 : s_H
- H 是一个整数,表示网格中的行数,H = 50 满足…
- W 是一个整数,表示网格中的列数,W = 50 满足…
- K 是一个整数,表示组成一块的方块数量, 最大为K = 8 满足…
- s_i (1 \leq i \leq H) 是网格 i 表示行数的长度 W 是字符串,
s_i 的任何字符
数量最多为
0减去9的整数。 s_i 可以得到第 j (1 \leq j \leq W) 字符是 表示 (i,\ j) 平方的整数。
出力
输出请按以下格式输出到标准输出。
C
y_{1,1} x_{1,1}
y_{1,2} x_{1,2}
:
y_{1,K} x_{1,K}
y_{2,1} x_{2,1}
y_{2,2} x_{2,2}
:
y_{C,K} x_{C,K}
- 第一行的件数 C 请输出。
- 继续 C \times K 在每行输出两个代表正方形位置的整数,用空格分隔。
- (c - 1) \times K + k \ (1 \leq c \leq C ,\ 1 \leq k \leq K) 第,c 用于第 片 k 第二个方块的位置 按顺序输出 (y_{c,k}, \ x_{c,k}) 的行和列,用空格分隔。
- 请连续输出同一块中使用的方块。
- 同一块中使用的方块可以按任意顺序输出。
- 同一块中使用的方块完全相同 请输出 K 件。
- 同一块中使用的方块必须相连。
- 每件都可以按任意顺序输出。
关于评分
对于每个测试用例,输出片段的总分除以 10,000,四舍五入到最接近的整数,成为该测试用例的分数。
总共有10个测试用例。每个测试用例的总分就是该题的得分。
入力例1
50 50 8 53201047392344411470438731252072209638476606576022 13242641632370617792332244270350675420864470404947 76372756316250650550563212732102937351075767336672 43391440260272522122049404306241926052045602433410 52720091423022222223344046324704721322132522334463 61693424425167321660472564434627234092497347246494 74134790436364436322363453027722019104342653173246 06407501031023661315440613726761261950342364317750 32434003036734297520344434846325625906542524345344 05729429300314444521730193634776225440322622762751 86170432967422452264329256425612350934624120326541 26260636676449250472787131576465747405632235055443 40432921056447267224144437767405026230355213327648 24472704922530039761140156512267320526045880236176 07436062226225795544236739634472433612487916576911 55028479331202644253542466261627757154341742036422 44736123293411696555237251437134202024002321292635 81006264110473511002519270476632234036184209203337 34270476462376904464776536713540006776077721473323 32686034469090324371414045247233600414023574431213 04080796152524541314625733207636637252102345120474 36904177763204264504704640313204912205748211284652 57646677253297155293792204031260531495473582235447 61433022620013614311260112334301203542233443703533 26244220666366257106223555253272744437143551534343 72304587152225442705443405915460720321040950035230 47266334792647716333950266050273713405293544063606 42436560231720147179723145056172462274137306344833 67443441401341276340150714410757027270244643654052 40404753669203250556387534301404004772563702525335 33666140790372604312034023231462405523170203279455 28102241646055944326071031547720270757259214611268 87746061343006140377547262199332060353244672704332 41225292920224383122136357428437525343572422270572 92160034046626479600394426924399953726374944127112 34214633560182413271544514253244940522222796462242 90062659764619121220592222437422113522730203122504 62132594362434364325233673235334175411672571335787 73620117121304602302723930343349513021441324772513 17763541417154976777536460213763760329204066378655 63263664266374779346744404484544692004111522323332 44632343821194331534223464082067723522091642446477 19604176094424473236373041633400242226774002570136 26233643026251007443132567680196513234006280452006 56654403268971142737776260023025532206663443245553 03675233864254722764052295365207973334724257032549 26647441241535162193323334617330476964344433334454 72463395769420225214343614245237240974142331159757 14226384625321023247202066906229042200415265466217 22420733370592047743255351070026772752224341534396
出力例1
2 1 1 2 1 1 2 1 3 2 3 3 3 4 3 4 2 5 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5
结果如下图所示。
第一首曲子的分数是 1620 来自1 \times 5 \times 3 \times 2 \times 2 \times 3 \times 3 \times 3 = 1620 。
第二首曲子的分数是 0 来自0 \times 3 \times 4 \times 7 \times 4 \times 9 \times 0 \times 0 = 0 。
因此,该测试用例的得分为 (1620+0)/10000=0.1620 向上舍入到最接近的整数。
发生器和测试仪
提供生成器和测试器,请从以下链接获取。
展示台
我们准备了一个可视化工具,可以计算分数并可视化输入和输出文件的结果。
- 此可视化工具已经过测试,可在主要浏览器上运行,但不能保证在所有环境中都能运行。
- 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
- 我们无法回应因使用此可视化工具而引起的任何问题。注意。
还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。