ストーリー

yukicoder国は大きな森を有する自然豊かな国である．

ある日，森を管理するmech_39君は予知夢を見た． それは明日，森のどこかに雷が落ち，森林火災が発生するというものであった． 季節柄，乾燥した木に雷が落ちれば延焼が起こり，火災は大規模になることが予想される．

そこで，mech_39君は森を守るために今日中にいくつかの木を伐採して延焼を防ごうと考えた． しかし，あまり多くの木を伐採してしまうと本末転倒である．

限られた本数の木を伐採して，焼失する木の本数の期待値を最小化せよ．

問題文

$N \times N$ のマス目からなる森がある．上から $i$ 行目・左から $j$ 列目のマスを $(i, j)$ $(0 \leq i, j < N)$ とする． 各マスには $0$ 以上 $9$ 以下の整数 $d_{i,j}$ が定められている．$d_{i,j} = 0$ のマスは湖や川で，木はない．$d_{i,j} \geq 1$ のマスには木が $1$ 本あり，$d_{i,j}$ はその木の乾燥度を表す．

明日，次のように森林火災が起こる．

1. 各木は，他と独立に確率 $d_{i,j} / 10$ で乾燥し，そうでなければ湿った状態になる．
2. $N^2$ マスの中から一様ランダムに選ばれた $1$ マスに雷が落ちる．
3. 雷が乾燥した木に落ちると，その木が燃え，火は上下左右に隣接する乾燥した木へ次々に燃え移る．湿った木や木のないマスには燃え移らない．

あなたは今日，木を最大 $K$ 本まで伐採できる．伐採したマスは木のないマスになり，燃えることも火を伝えることもない．

焼ける木の本数の期待値 $E$ ができるだけ小さくなるように，伐採する木を選択せよ．

得点

一本も木を伐採しない場合の期待焼失本数を $E_0$ とすると，以下のスコアを得る．スコアは大きいほどよい． $$\mathrm{round}\left(10^6 \times \left(1 + \log_2 \frac{E_0}{E}\right)\right)$$

補足

伐採されていない乾燥した木の 4 近傍連結成分を $C_1, C_2, \ldots$ とする．成分 $C_k$ に雷が落ちる確率は $|C_k| / N^2$ で，そのとき $|C_k|$ 本が焼けるので， $$E = \mathbb{E}\left[\frac{1}{N^2} \sum_{k} |C_k|^2\right]$$ となる．

$E$ と $E_0$ を厳密に計算することは困難なため，ジャッジは乾燥状態を $40000$ 回独立にサンプリングし，各サンプルで伐採あり・なしの両方について上式の期待値を計算した平均で $E$, $E_0$ を近似する（同じサンプルを共用するので，伐採しなければ必ず $E = E_0$ となる）． 乱数のシードは入力ごとに固定されており，同じ出力には常に同じ得点が付く．

テストケースは $50$ ケースあり，各テストケースの得点の合計が提出の得点となる． 一つ以上のテストケースで不正な出力や制限時間超過をした場合，提出の得点は $0$ 点となる． コンテスト時間中に得た最高得点で最終順位が決定され，コンテスト終了後のシステムテストは行われない．

入力

$N$ $K$
$d_{0,0}d_{0,1}...d_{0,N-1}$
$\vdots$
$d_{N-1,0}d_{N-1,1}...d_{N-1,N-1}$

• $N$ は森のサイズを表し，$N=50$ である．
• $K$ は伐採できる木の本数の上限で，$K=100$ である．
• $d_{i,j}$ は $(i,j)$ の木の有無，木の乾燥度を表す整数で，$0 \leq d_{i,j} \leq 9$ を満たす．

出力

伐採する木の本数を $M$ $(0 \leq M \leq K)$，伐採する木のマスを $(i_0, j_0), \ldots, (i_{M-1}, j_{M-1})$ として，以下の形式で出力せよ． 各 $(i_k, j_k)$ は $d_{i_k, j_k} \geq 1$ を満たす相異なるマスでなければならない．

15:17追記 木でないマスを伐採するとWAになります．ビジュアライザやテスターの挙動には問題ありません．

$M$
$i_0 \quad j_0$
$\vdots$
$i_{M-1} \quad j_{M-1}$

サンプル

50 100
66656634224434333444323423443888987978788777977999
66444624423232242224232424243989887988877987979878
56564642242234324342234344343999899789789798778898
65666463343422424322243344432999999888789789899778
55545464242234332224244422244899988999778878799998
44544444343342444434434334223998889999978977877988
06454562232442333332243333232999899998899897777977
04456659344423232342323224243988999898898778889779
00656659343334424422344332423989999998898777787887
40556569842444243234433344224298999998999888779778
60445589992442332433322322244299899998998899899897
60000599989223332334222332444488899999998889877877
54640599899932322342332223242288999898999897778788
65440099999992422443232223422299998898989878898979
55654009999893234332333222324453544344334497889978
45465098898999423432432433422993344555443588897977
45569000889999844424234434399995333534454359889898
45569990099899892233324242999989335345545339877889
55459900899899888333333488989989335334355537989799
55558909999999999932338888989985545354534378697889
55589809889988999993499999889955668767777666666768
64599808988999989999899999999665558866876678868887
44599800989999998981399989996755566778866766866678
64898890998998989992221899876767664768786777666788
45999900999898999833121238555557544587667767768788
55899909999898997791333331565555466648678688786886
59999808989997879873222221676764666566778677766786
59999900998887798799333211675746455565777876668676
58999900977988797799731337766655456556687768766868
99999800997789797989921775756554654665686667678777
99998980007888999897986757766565644465546686898787
99899453008007777899986775777775456446457889988987
99335535030000097897878667575764445656588989778779
63453345000000008787778877676654554546577877899978
77554433500000008878668876566577455577598789987779
76534334400000009797866667855557755765689989778979
75565543400000009888677878687656576675777987898879
77655444300000009878866768877675676576689787779877
77665755530000037766686778878675665677679789998788
76766668666888883988688886788856555567667988998988
67757558687886788776867678676876657656758989988988
87567565677878677667676686868855567776777898879888
77655667656787687766768787778667787677678888999899
67565756655777787886878776788867776768676879988899
66556755577557766887686667798987687687877899899898
86657577565776568868687689989966777688767699989989
77565666556667675886678998889868677867766789998998
88777657776775765578789888888677688687887899988999
87667665555566775686898899997575868877788689998899
77675575776566576689999989955567787687777888999888

3
0 32
1 33
2 34

入力生成方法

$\mathrm{rand}(L, U)$ は $L$ 以上 $U$ 以下の整数を，$\mathrm{randf}(L, U)$ は $L$ 以上 $U$ 未満の実数を一様ランダムに生成する関数とする．

$\bold{乾燥度の生成}$
$30$ 個の点 $p_1, \ldots, p_{30}$ を置く．各点の座標 $(y_k, x_k)$ は，$y_k = \mathrm{randf}(0, 50)$，$x_k = \mathrm{randf}(0, 50)$ とする．値の列「$2, 3$ を $1$ 個ずつ，$4, 5$ を $2$ 個ずつ，$6, 7, 8, 9$ を $6$ 個ずつ」（計 $30$ 個）をランダムに並べ替えて $p_1, \ldots, p_{30}$ に割り当てる．

各マス $(i, j)$ について，点 $(i + 0.5, j + 0.5)$ からのユークリッド距離が最も小さい点 $p_k$（距離が等しい点が複数あれば $k$ が最小のもの）の値に $\mathrm{rand}(-1, 1)$ を加え，$1$ 以上 $9$ 以下に切り詰めたものを $d_{i,j}$ とする．

$\bold{湖の生成}$
$\mathrm{rand}(1, 4)$ 個作る．各湖は中心の座標 $(y, x)$ を $y = \mathrm{randf}(0, 50)$，$x = \mathrm{randf}(0, 50)$，半径 $r$ を $\mathrm{randf}(2, 5)$ で選び，点 $(i + 0.5, j + 0.5)$ と中心のユークリッド距離が $r$ 未満のマスを $d_{i,j} = 0$ に上書きする．

$\bold{川の生成}$
$\mathrm{rand}(0, 2)$ 本作る．各川は，湖を $1$ つ一様ランダムに選び，その中心を含むマスから流れ出す．流れる向き $v$ を上下左右から一様ランダムに選び，盤面の外に出るまで次を繰り返す．

• 今いるマス $(i, j)$ を $d_{i,j} = 0$ に上書きする．
• 確率 $1/2$ で $v$ の向きに，確率 $1/4$ ずつで $v$ を左または右に $90$ 度回した向きに，$1$ マス進む．

ツール(入力ジェネレータ・ビジュアライザ)

• Web版ビジュアライザ：入力の生成，得点の計算，可視化ができます．
• ローカル版：使用するにはRust言語のコンパイル環境をご用意下さい．使い方は同梱の README を参照してください．

生成AIの利用について

生成AIの利用については，AtCoderのAHC GenAI Rules Trial Contest 2026に準じます．指定されているプロンプトを必ず含めるようにしてください．

簡単に述べると，生成AIを解法の考察に用いることは禁止としますが，実装のみを任せることは許容します．