RCO presents 日本橋ハーフマラソン 予選

A - Multiple Pieces


Time limit時間制限 : 10sec / Memory limitメモリ制限 : 1024MB

背景

※この「背景」の項に書かれている文章は問題とあまり関係がありません。問題文は「問題文」の項から始まります。

20XX 年、RCO 量子サーバールーム ━━━ ここには RCO の持つ大量の量子コンピュータが所狭しと並んでいる。

2016 年に量子コンピューティングに参入した RCO アドテク部は、2017 年には実際の量子コンピュータ上で機械学習プログラムを走らせたり、量子アニーリングの国際学会のホストを務めるなどして勢いを増し、この時代では量子コンピュータ専門の企業になっていた。

競技プログラミングの経験を買われて入社した社員 X は、広告マッチングシステムの高速化に携わっていたが、今やその仕事も量子コンピュータに取って代わられ、プログラミングの仕事を失った彼は量子コンピュータを接続する仕事をしている。

RCO の長年の研究によって、量子コンピュータには以下の性質があることが明らかになった。

  • 量子コンピュータは K 台連結することによって、その力を発揮する。 K 台より多くても少なくても機能しない。この連結した K 台を「ピース」と呼ぶ。
  • あるピースに含まれる量子コンピュータは、別のピースに含むことができない。
  • ピースのもつ力は、ピース内の各量子コンピュータの能力の積に等しい。

このサーバールームには HW 列のグリッド状に H \times W 台の量子コンピュータが並んでいて、社員 X の仕事は、どの量子コンピュータを接続するか決めることである。量子コンピュータは、辺で接している隣の量子コンピュータとしか接続できない。接続された量子コンピュータを辿って到達できる時、それらの量子コンピュータは連結であるといえる。

社員 X は適切にピースを作ることで、全てのピースの力の合計を最大化したいが、プログラミングの仕事を失った彼はプログラミング能力も失ってしまった!そこで、彼の親しい友人であるあなたが、そのプログラムを書いてあげることにした。

問題文

同じ大きさの正方形のマスが HW 列並んだ長方形のグリッドがあります。1 \leq i \leq H, 1 \leq j \leq W を満たす整数 ij について、 ij 列に位置するマスの座標を (i,\ j) と表します。各マスには 0 以上 9 以下の整数が 1 つ書かれています。

このグリッド上で、いくつかのピースを作ります。ピースとは、ちょうど 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 は 1 つのピースを作るマスの数を表す整数であり、K = 8 を満たします。
  • s_i (1 \leq i \leq H) はグリッドの i 行目を表す長さ W の文字列であり、 s_i を構成する文字はいずれも 0 から 9 までの整数です。 s_ij (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}
  • 1 行目にピースの数 C を出力してください。
  • 続く C \times K 行には、各行にスペース区切りで、マスの位置を表す 2 つの整数を出力してください。
  • (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

この結果は、下の図のようになります。

1 個目のピースのスコアは、1 \times 5 \times 3 \times 2 \times 2 \times 3 \times 3 \times 3 = 1620 より 1620 です。

2 個目のピースのスコアは、0 \times 3 \times 4 \times 7 \times 4 \times 9 \times 0 \times 0 = 0 より 0 です。

よって、このテストケースの得点は (1620+0)/10000=0.1620 の、小数点以下を切り上げて 1 となります。

ジェネレータとテスター

ジェネレータとテスターを次のリンクから提供しています。

ジェネレータ・テスター

ビジュアライザ

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

  • このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。
  • このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
  • このビジュアライザを使用したことで発生したトラブルには対応できません。ご了承ください。

ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。

ビジュアライザ


Submit提出する