HACK TO THE FUTURE 2021 本選オープンコンテスト

A - マイニング

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

未来社は鉱山から鉱石を採掘するマイニング事業を行っている。今から採掘する予定の鉱山は真上から見て50行50列の正方形状に並んだブロックで表され、各ブロックごとに採掘した際に得られる利益が事前調査により明らかになっている。採掘はブロック単位で行い、同時に複数ブロックを採掘することは出来ない。

ブロックを新たに採掘するためには、4方向に隣接するブロックのうち、少なくとも一つ以上が採掘済みでなければならない。ただし、鉱山の外部は全て採掘済みとして扱う。作業スペースが広いほど採掘が容易になるため、採掘のコストは採掘予定のブロックに隣接する採掘済みブロック数 k に依存し、入力で与えられる採掘コスト係数 C を用いて、C/k のコストがかかる。

例えば3行3列のブロックからなる鉱山において、下図の1,2,3,4,5の順で採掘を行った場合、それぞれ C/2, C/2, C/1, C/2, C/3 のコストがかかる。鉱山の外部は採掘済みとして扱うため、1つ目と2つ目の採掘における隣接する採掘済みブロック数はともに上方向と左方向の2つであることに注意せよ。

12.
.34
..5

どのブロックをどのような順番で採掘するかの計画を建て、利益ーコストを出来るだけ大きくせよ。利益の総和が p、コストの総和が c のとき、\max(0, p - c) 点が得られる。テストケースは全部で100個あり、各テストケースの得点の合計がその提出の得点となる。一つ以上のテストケースで不正な出力(隣接ブロックが採掘済みでないブロックを採掘するなど)をした場合、提出全体の判定がWAとなる。

入力

入力は以下の形式で標準入力から与えられる。

C
p_{0,0} p_{0,1} \ldots p_{0,49}
\vdots
p_{49,0} p_{49,1} \ldots p_{49,49}

C は採掘コストの係数で、12の倍数である。 p_{i,j} は i 行目 j 列目のブロックを採掘した際に得られる利益を表す非負整数である。値の範囲や生成方法については後の項目を参照せよ。

出力

採掘するブロックの総数を M 、k 番目に採掘するブロックの行番号を i_k (0\leq i_k \leq 49)、列番号を j_k (0\leq j_k \leq 49) としたとき、以下の形式で出力せよ。

M
i_1 j_1
\vdots
i_M j_M

入力生成方法

a 以上 b 以下の整数を一様ランダムに生成する関数を rand(a, b) で表す。

C の生成

採掘コスト係数 C の値は 12 × rand(25, 35) で生成される。

p の生成

各ブロックの採掘利益を表す行列 p は以下のように生成される。 i=0, i=49, j=0, j=49 のいずれかを満たす座標 (i, j) を外周と呼ぶことにする。外周は p_{i,j}=0 で固定する。まずはじめに、外周以外のブロック 1\leq i\leq 48, 1\leq j\leq 48 に対して独立に、p_{i,j}= rand(0, 200) と初期化する。次に、以下の操作を100回繰り返して鉱脈を生成する。

鉱脈の開始位置 i= rand(3, 46) と j= rand(3, 46) を生成する。
鉱脈の大きさを表す2つのパラメータ w= rand(10, 20) と h= rand(100, 300) を生成する。
以下の操作を w 回繰り返す。
1. p_{i,j} の値を rand(0, h) 増やす。
2. 現在位置 (i,j) の4方向に隣接するブロックのうち、外周でないものの中から一様ランダムに1つブロック (i',j') を選び、(i,j)=(i',j') と置き換える。

入力例 1

372
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 158 95 186 91 192 190 34 65 66 22 26 85 133 32 119 21 117 148 340 195 30 65 111 167 93 25 21 42 193 107 161 43 133 165 4 83 95 245 390 41 29 244 197 139 49 62 118 11 0
0 122 108 143 67 18 42 7 38 165 3 28 185 68 5 144 145 156 464 266 21 35 164 138 61 163 14 165 129 199 119 121 222 586 372 120 12 232 434 221 150 428 376 53 98 187 193 16 191 0
0 46 88 25 94 66 4 40 67 87 343 194 72 101 42 329 531 304 482 243 106 40 165 96 28 167 22 45 23 113 163 172 374 345 175 67 27 105 605 345 84 252 532 105 4 197 116 159 46 0
0 57 179 149 193 364 173 200 129 214 237 365 349 443 30 42 407 124 189 213 188 47 21 197 56 161 45 98 72 321 484 151 162 205 85 4 106 313 400 276 73 291 161 205 286 35 109 78 46 0
0 54 106 236 282 54 55 103 92 52 287 525 567 213 269 8 271 183 154 137 189 89 186 63 42 139 1 158 211 205 273 482 165 45 184 79 148 365 218 295 561 134 2 159 30 11 174 192 165 0
0 29 18 41 160 42 102 55 140 30 89 278 252 61 418 74 450 155 65 104 93 15 66 200 43 97 183 55 322 347 338 246 321 113 18 195 248 199 132 407 283 19 12 101 61 144 174 58 36 0
0 94 17 118 242 0 87 46 31 189 135 1 179 176 102 143 212 94 210 152 120 410 14 102 35 110 614 433 49 357 202 173 124 395 163 585 64 65 128 603 171 456 96 211 175 79 197 63 112 0
0 158 145 283 54 158 23 50 56 43 37 162 135 167 134 76 0 4 294 92 201 317 83 271 193 54 166 285 298 182 72 135 351 853 200 392 150 93 40 118 190 149 334 251 37 172 155 19 78 0
0 114 121 282 200 345 388 168 141 104 126 195 317 89 151 66 198 195 181 297 254 353 169 152 334 247 46 46 8 77 183 197 260 527 144 48 140 217 135 99 364 164 275 424 206 264 68 197 104 0
0 106 22 94 333 450 169 101 168 195 522 471 369 190 179 284 101 121 90 472 278 224 296 333 271 23 92 120 194 131 26 92 397 337 203 24 141 564 138 159 45 144 184 325 195 440 177 132 48 0
0 40 270 395 468 638 187 95 174 185 323 560 347 150 99 27 179 188 430 452 150 151 199 201 61 112 217 181 19 46 37 382 386 113 83 166 120 499 296 176 75 7 12 243 6 521 205 193 116 0
0 182 152 358 545 283 231 73 134 77 24 136 18 325 375 245 103 198 280 120 351 190 160 189 188 162 109 8 116 249 142 213 392 356 313 34 137 222 265 84 310 71 198 83 395 163 479 200 61 0
0 97 97 41 206 300 532 175 61 157 60 180 44 149 200 81 180 192 129 207 417 83 380 105 91 161 130 178 82 58 205 182 329 236 340 559 693 623 262 190 230 187 65 221 511 583 182 282 76 0
0 85 101 21 190 161 233 99 170 31 34 162 153 176 2 167 161 68 63 97 337 349 382 363 346 173 239 121 147 54 49 64 101 65 184 71 192 149 77 248 361 406 425 200 318 732 308 15 130 0
0 75 32 94 20 88 9 193 48 196 7 36 144 172 29 165 146 69 86 185 77 175 327 222 235 304 204 21 63 42 118 169 161 10 186 162 217 336 211 403 493 494 121 376 123 231 73 193 132 0
0 1 188 178 166 0 36 195 74 76 114 148 197 112 130 199 174 154 145 80 141 41 237 200 182 22 190 10 150 321 227 119 30 183 267 228 186 57 150 116 350 313 117 9 166 15 19 19 3 0
0 16 66 155 55 125 26 12 175 13 182 104 126 160 152 168 78 5 164 22 13 1 266 30 130 185 83 157 247 181 197 103 94 197 135 119 164 231 94 185 48 135 85 132 48 164 10 13 49 0
0 151 63 197 8 57 177 69 15 11 68 25 191 130 71 50 138 180 200 193 122 13 30 141 41 99 144 14 283 120 191 117 28 36 6 52 68 119 125 172 268 159 124 178 104 85 35 94 66 0
0 190 34 82 31 73 124 167 160 172 147 75 62 129 54 108 101 39 98 157 198 159 169 27 75 107 140 98 171 206 307 302 123 37 175 38 123 64 178 170 43 88 185 33 180 73 37 6 135 0
0 44 38 145 163 131 94 98 36 113 213 29 6 41 58 159 93 109 188 123 227 425 92 63 50 109 182 67 21 4 250 410 19 85 9 135 144 137 23 358 293 263 51 21 89 188 140 56 37 0
0 145 144 157 28 99 285 375 411 159 197 0 86 103 38 167 116 105 36 168 203 294 12 174 295 103 190 46 156 35 127 75 264 98 39 138 186 127 84 222 270 311 89 155 74 183 87 72 115 0
0 174 196 95 255 372 487 296 359 268 62 121 178 41 101 165 137 128 15 7 56 235 176 371 273 193 16 113 141 122 156 285 410 117 48 165 90 536 20 89 105 64 133 68 26 139 103 90 166 0
0 65 137 211 261 402 434 395 44 2 164 61 109 15 193 159 17 115 199 102 30 10 123 124 153 120 15 168 48 0 91 65 230 96 181 112 67 1035 797 162 63 0 149 111 41 53 44 164 98 0
0 174 122 271 377 647 324 71 50 25 26 100 83 165 78 70 87 155 13 83 31 170 490 564 44 95 204 125 114 182 61 122 208 28 142 200 147 342 313 409 277 148 294 33 107 4 150 30 108 0
0 49 195 15 39 330 379 152 143 183 61 78 28 147 56 196 104 160 3 151 17 23 191 302 328 318 433 55 196 7 155 108 201 8 126 78 180 61 161 285 188 208 241 276 217 187 45 60 59 0
0 48 159 37 115 26 6 196 25 162 166 131 163 33 64 16 155 105 53 43 135 42 101 119 88 292 104 178 1 180 35 105 55 64 27 85 0 77 100 196 61 208 254 145 328 283 45 91 153 0
0 57 113 48 4 165 37 148 81 189 50 109 8 24 63 92 117 183 64 36 10 27 31 73 253 695 157 529 819 328 10 134 9 44 105 132 67 549 153 169 98 180 112 14 131 151 159 51 99 0
0 61 84 49 161 128 187 164 94 186 74 164 194 25 62 40 92 51 66 11 35 64 171 31 121 285 160 793 382 132 95 169 23 41 202 387 642 542 485 159 53 85 122 118 89 363 242 43 96 0
0 70 153 114 13 33 191 139 93 58 93 131 9 4 138 87 55 15 47 199 24 51 32 155 244 282 271 418 223 151 143 134 25 211 307 366 202 450 815 286 187 32 64 28 489 192 108 156 161 0
0 47 102 26 194 117 180 117 174 138 132 110 35 87 335 129 338 268 202 88 8 85 195 11 187 278 340 464 452 359 140 60 39 10 173 264 157 334 253 186 237 104 120 208 489 282 200 45 154 0
0 11 170 20 30 140 158 111 25 11 76 142 53 139 139 43 113 431 851 165 125 68 92 9 10 153 151 118 194 355 119 107 61 62 40 126 67 175 200 11 154 175 48 88 44 381 76 195 362 0
0 196 152 100 78 183 13 118 24 192 101 88 1 186 42 84 210 312 521 789 201 69 27 16 80 34 26 66 181 427 288 39 62 66 169 81 106 10 175 133 72 25 116 155 100 103 48 624 559 0
0 194 516 167 188 84 319 210 544 117 181 41 72 15 27 19 141 332 54 645 181 127 92 97 116 38 8 183 95 410 450 48 150 166 170 62 68 27 162 16 28 198 15 228 154 216 79 534 64 0
0 396 473 256 129 355 785 736 386 114 29 149 30 162 92 229 538 198 242 330 150 173 81 53 22 14 160 227 193 353 255 104 184 187 190 41 99 18 4 286 304 357 86 6 176 110 334 320 88 0
0 134 124 374 288 15 187 431 170 140 231 27 186 73 0 43 228 528 38 182 61 124 37 90 129 23 118 724 580 70 162 133 166 175 61 161 152 32 95 132 433 518 174 134 41 602 623 192 151 0
0 18 74 579 88 77 74 44 109 92 173 265 513 223 127 193 2 238 80 135 33 59 133 173 46 135 287 322 695 23 82 72 14 192 70 88 59 35 145 103 104 364 187 19 143 148 15 59 76 0
0 86 86 227 129 128 78 56 88 192 153 283 396 278 29 192 597 236 169 114 169 182 171 313 360 571 479 378 421 251 327 286 158 97 249 126 190 37 150 48 0 300 47 222 252 66 128 158 168 0
0 176 71 195 268 80 144 87 65 156 89 162 168 50 184 127 392 500 255 83 75 188 52 402 469 451 535 493 225 18 127 123 100 200 268 496 284 205 303 308 88 94 341 409 665 405 274 137 345 0
0 37 168 123 301 141 6 47 104 3 125 75 159 69 26 174 152 145 89 0 68 478 224 542 909 1014 506 234 10 145 36 141 50 9 186 93 205 284 152 71 81 138 57 196 370 111 145 119 374 0
0 183 6 85 76 174 40 2 174 42 164 139 181 269 189 189 79 171 114 193 104 39 313 479 383 440 463 186 148 105 71 121 109 148 90 40 167 292 241 132 190 174 65 68 197 15 14 93 562 0
0 91 141 201 540 138 213 279 197 28 136 248 238 255 197 23 46 61 292 312 159 230 94 138 6 97 203 101 50 79 139 35 135 81 109 51 18 68 43 145 173 27 150 1 180 169 49 199 174 0
0 34 129 499 190 328 323 106 134 112 452 88 254 235 125 107 50 38 170 468 598 156 187 148 113 52 120 143 72 36 110 142 127 86 180 10 20 123 5 3 33 122 46 22 87 166 84 98 126 0
0 177 169 147 269 194 348 1 119 266 531 204 276 261 66 62 477 363 461 594 496 331 451 272 196 185 139 37 290 76 144 23 153 175 61 149 90 199 23 79 141 133 168 135 178 65 57 97 124 0
0 158 123 225 170 186 531 9 224 255 529 130 328 290 434 277 736 372 202 360 284 1 239 435 192 27 102 341 418 64 77 142 184 147 205 65 254 75 18 194 175 98 81 61 173 182 119 198 193 0
0 184 81 173 231 341 142 41 49 77 28 194 214 154 330 58 438 462 428 193 230 70 67 15 175 89 29 315 396 119 3 45 110 88 265 256 154 85 195 72 24 13 112 173 167 0 16 1 178 0
0 147 127 76 150 11 153 39 47 55 59 63 176 78 267 87 88 7 117 14 383 46 180 186 124 109 20 134 145 185 148 81 466 373 207 435 174 31 35 123 98 96 22 75 196 113 132 120 50 0
0 194 18 36 30 108 50 191 159 68 135 15 159 134 133 188 75 166 10 70 195 175 115 14 3 32 173 38 181 102 62 127 140 256 319 432 172 139 24 45 187 141 308 57 29 159 164 27 63 0
0 59 53 194 47 16 105 164 98 29 9 179 57 9 127 154 54 152 178 186 103 84 48 124 67 139 2 0 16 107 187 127 138 188 186 63 181 10 127 131 179 6 90 79 133 100 49 78 153 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 1

B - ビジュアライザ

Time Limit: 0 msec / Memory Limit: 0 KB

配点 :0点

A問題「マイニング」のビジュアライザ用のページです。問題ページではないので回答不要です。

テストケース生成

乱数シードを指定し、ローカル実行用に指定した数のテストケースを生成・ダウンロードできます。
生成されるテストケースは、指定したシード値から1つずつ増やしたものです。
例：「Seed= 20201212、ケース数= 3」の時、各ケースのシード値は順に「20201212, 20201213, 20201214」となります。

本機能はchrome上での動作を想定しています。他の環境で正常に動作する保証はなく、特にIEでは動作しないことを確認しています。
本機能は当コンテスト上でのテストケースとの同一性を保証するものではありません。特に入力順序や乱数生成の仕様に差異があることが考えられますので、予めご了承ください。

Seed=

ケース数=

ビジュアライザー

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

本ビジュアライザはchrome上での動作を想定しています。他の環境で正常に動作する保証はなく、特にIEでは動作しないことを確認しています。
本ビジュアライザから解答の提出はできません。 AtCoder A問題「マイニング」上より解答を提出して下さい。
本ビジュアライザ上で計算された点数は、当コンテスト上での点数を保証するものではありません。本ビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
テキストファイルの改行コードはLFを想定しています。特にWindowsをご使用の方はご注意下さい。
マウスオーバーで各マスの座標を(列,行)で表示します。

問題文中の入出力例はこちら(zip)

入力ファイル：

出力ファイル：

Score

簡易描画

未採掘マス

：利益=0

：利益=コスト

：利益=1000

：採掘済みマス