テストケース数

50 個

入力生成方法

K=100、B=10 で固定する。 印の座標は、まだ印の付いていない座標の中から一様ランダムに選択することで生成する。 ただし、1つ目の印は上端 (i_1=0)、2つ目の印は左端 (j_2=0)、3つ目の印は下端 (i_3=N-1)、4つ目の印は右端 (j_4=N-1) の中に絞り込んで一様ランダムに選択する。

各ポリオミノは以下のように生成する。 ポリオミノを構成する各正方形をブロックと呼ぶことにする。 1つ目のポリオミオは1ブロックからなり、コストはC_1=15とする。 b (2\leq b\leq B) 番目のポリオミノは 2(3+b) ブロックからなり、コストは C_b=\mathrm{round}(15\sqrt{2(3+b)}) で、1ブロックのポリオミノから開始して以下の拡張操作を 2(3+b)-1 回繰り返すことで生成する。

1. 拡張する方向を上下左右の4方向の中から一様ランダムに選択する。
2. その方向に向かって一番端にあるブロックの中から一様ランダムに選択し、その方向に隣接するマスをポリオミノに含めることで1ブロック拡張する。

ツール

• Web版ビジュアライザ・入力ジェネレータ
• ローカル実行版ビジュアライザ・入力ジェネレータ: 使用するには、Rust言語のコンパイル環境をご用意下さい。

入力例 1

50 100 10
0 25
1 0
49 21
49 49
0 43
41 9
26 6
5 26
12 32
38 33
13 4
16 7
17 28
41 14
36 28
16 11
2 46
25 18
40 46
33 42
5 9
17 45
27 23
26 48
9 14
6 22
29 37
17 11
12 42
0 32
46 40
7 43
35 27
30 33
3 40
34 14
7 20
37 32
12 38
4 41
28 17
16 46
36 29
29 35
41 21
26 14
28 5
22 7
0 24
25 10
19 22
45 15
16 19
46 2
40 39
8 34
46 19
33 29
2 35
29 46
16 43
49 39
21 34
12 0
25 49
33 30
20 9
35 42
19 15
24 35
24 30
8 5
45 4
37 38
46 20
16 45
15 5
45 49
4 2
18 45
37 8
13 49
13 32
28 26
41 6
42 3
17 43
21 16
14 13
0 33
15 24
11 32
11 15
16 30
20 12
26 38
0 19
23 0
29 30
46 22
1 1 15
#
8 3 47
..#
..#
..#
###
..#
..#
..#
..#
6 7 52
....#..
#######
.#.....
.#.....
.#.....
.#.....
8 7 56
......#
#######
...#...
...#...
...#...
...#...
...#...
...#...
5 12 60
.......#....
.......#####
########....
.....#......
.....#......
13 6 64
...#..
...#..
...#..
...#..
...#..
...#..
...###
####..
...#..
...#..
...#..
...#..
...#..
10 11 67
.........#.
.........#.
.........#.
.........#.
##########.
.........##
.........#.
.........#.
.........#.
.........#.
13 10 70
...#......
...#......
####......
...##.....
....#.....
....#.....
....#.....
....###...
......#...
......#...
......####
......#...
......#...
10 15 73
..........#....
..........#....
..........#....
..........#####
###########....
........#......
........#......
........#......
........#......
........#......
12 15 76
........#......
........#......
........#......
........#......
........#......
........#......
........#......
#########......
........#######
........#......
........#......
........#......

出力例 1

392
1 0 25
1 0 24
1 12 32
1 13 32
1 11 32
1 36 28
1 36 29
1 16 11
1 17 11
1 17 45
1 16 45
1 18 45
1 0 32
1 0 33
1 16 46
1 46 19
1 46 20
1 33 29
1 33 30
1 16 43
1 17 43
1 38 33
1 37 33
1 37 32
1 35 28
1 35 27
1 33 42
1 34 42
1 35 42
1 16 44
1 26 48
1 25 48
1 25 49
1 29 37
1 29 36
1 29 35
1 3 40
1 3 41
1 4 41
1 46 21
1 46 22
1 41 9
1 41 8
1 41 7
1 41 6
1 26 6
1 26 5
1 27 5
1 28 5
1 13 4
1 13 5
1 14 5
1 15 5
1 16 7
1 15 7
1 15 6
1 17 28
1 16 28
1 16 29
1 16 30
1 9 14
1 9 15
1 10 15
1 11 15
1 6 22
1 6 21
1 6 20
1 7 20
1 30 33
1 29 33
1 29 34
1 34 28
1 33 28
1 46 2
1 45 2
1 45 3
1 45 4
1 20 9
1 20 10
1 20 11
1 20 12
1 19 15
1 19 16
1 20 16
1 21 16
1 49 21
1 48 21
1 47 21
1 49 49
1 48 49
1 47 49
1 46 49
1 45 49
1 16 8
1 16 9
1 16 10
1 15 11
1 14 11
1 14 12
1 14 13
1 25 18
1 25 17
1 26 17
1 27 17
1 28 17
1 27 23
1 27 24
1 27 25
1 27 26
1 28 26
1 28 37
1 27 37
1 26 37
1 26 38
1 18 11
1 19 11
1 12 42
1 12 41
1 12 40
1 12 39
1 12 38
1 46 40
1 46 39
1 47 39
1 48 39
1 49 39
1 29 32
1 29 31
1 29 30
1 36 32
1 36 31
1 36 30
1 22 7
1 21 7
1 20 7
1 20 8
1 40 39
1 39 39
1 38 39
1 37 39
1 37 38
1 2 35
1 1 35
1 0 35
1 0 34
1 21 34
1 21 35
1 22 35
1 23 35
1 24 35
1 32 30
1 31 30
1 30 30
1 19 14
1 19 13
1 19 12
1 44 3
1 43 3
1 42 3
1 41 5
1 41 4
1 41 3
1 1 0
1 1 1
1 1 2
1 2 2
1 3 2
1 4 2
1 0 43
1 0 44
1 0 45
1 0 46
1 1 46
1 2 46
1 41 10
1 41 11
1 41 12
1 41 13
1 41 14
1 40 8
1 39 8
1 38 8
1 37 8
1 25 6
1 24 6
1 23 6
1 22 6
1 25 7
1 25 8
1 25 9
1 25 10
1 5 26
1 5 25
1 5 24
1 5 23
1 5 22
1 12 4
1 12 3
1 12 2
1 12 1
1 12 0
1 41 15
1 42 15
1 43 15
1 44 15
1 45 15
1 26 16
1 26 15
1 26 14
1 26 47
1 26 46
1 27 46
1 28 46
1 29 46
1 12 43
1 13 43
1 14 43
1 15 43
1 7 43
1 6 43
1 5 43
1 4 43
1 4 42
1 25 37
1 24 37
1 24 36
1 24 17
1 23 17
1 22 17
1 21 17
1 0 23
1 0 22
1 0 21
1 0 20
1 0 19
1 45 16
1 45 17
1 45 18
1 45 19
1 8 34
1 8 33
1 8 32
1 9 32
1 10 32
1 24 34
1 24 33
1 24 32
1 24 31
1 24 30
1 13 31
1 13 30
1 14 30
1 15 30
1 28 27
1 28 28
1 28 29
1 28 30
1 13 13
1 12 13
1 11 13
1 11 14
1 1 22
1 2 22
1 3 22
1 4 22
1 1 43
1 2 43
1 3 43
1 12 33
1 12 34
1 12 35
1 12 36
1 12 37
1 37 34
1 37 35
1 37 36
1 37 37
1 11 4
1 10 4
1 9 4
1 8 4
1 8 5
1 15 28
1 15 27
1 15 26
1 15 25
1 15 24
1 11 43
1 10 43
1 9 43
1 8 43
1 2 40
1 2 39
1 2 38
1 2 37
1 2 36
1 13 44
1 13 45
1 13 46
1 13 47
1 13 48
1 13 49
1 41 21
1 42 21
1 43 21
1 44 21
1 45 21
1 19 22
1 18 22
1 17 22
1 16 22
1 16 21
1 16 20
1 16 19
1 15 22
1 15 23
1 35 41
1 35 40
1 35 39
1 36 39
1 0 26
1 0 27
1 0 28
1 0 29
1 0 30
1 0 31
1 40 14
1 39 14
1 38 14
1 37 14
1 36 14
1 35 14
1 34 14
1 27 18
1 27 19
1 27 20
1 27 21
1 27 22
1 40 46
1 40 45
1 40 44
1 40 43
1 40 42
1 40 41
1 40 40
1 5 9
1 5 8
1 5 7
1 5 6
1 5 5
1 6 5
1 7 5
1 45 39
1 44 39
1 43 39
1 42 39
1 41 39
1 16 18
1 16 17
1 16 16
1 17 16
1 18 16
1 4 5
1 4 4
1 4 3
1 40 47
1 40 48
1 40 49
1 41 49
1 42 49
1 43 49
1 44 49
1 26 39
1 26 40
1 26 41
1 26 42
1 26 43
1 26 44
1 26 45
1 33 14
1 32 14
1 31 14
1 30 14
1 29 14
1 28 14
1 27 14
1 23 5
1 23 4
1 23 3
1 23 2
1 23 1
1 23 0