RCO presents 日本橋ハーフマラソン 本戦 (オープン)

B - 日本橋大渋滞


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

問題文

HW 列のマスからなるマップがあります。そのうち K 個のマスには、1台の車があります。

一番上の行を 1 行目、一番左の列を 1 列目とし、rc 列にあるマスを (r, c) と表します。

K 台の車それぞれに、最初にいるマス(初期マスと呼ぶ)と目的地となるマス(目的マスと呼ぶ)が与えられます。車 i の初期マスは (A_i, B_i) です。また、車 i の目的マスは (C_i, D_i) です。 あなたはそれぞれの車に対して、各時刻 t (0 \leq t \lt L, tは整数) で辺で隣接したマスへの移動を指示できます。すると、時刻 t+1 で、その車は指示されたマスに移ります。ただし、以下のような移動を指示することはできません。

  • 移動先のマスに時刻 t の時点で車が存在する場合
  • 同時に複数の車の移動先が同じマスになる場合
  • 移動先がマップの外側になる場合

1回の指示で、K 台全ての車それぞれに対して、隣接した4方向への移動を指示、あるいは、移動せず、今いるマスに留まることを指示します。最大で T 回指示を出すことができます。

各テストケースの得点および、この問題の得点は、次のように計算されます。

  • あるテストケースでの車 i の最終的な位置を (r_i, c_i) として、 とします。
  • 指示回数を L (0 \leq L \leq T) として P_T = 10 + L \times 0.01 とします。
  • score = 10^7 / (P_D \times P_T)
  • 上記の計算で算出した score の小数点以下を切り上げたものが、そのテストケースでの最終的な得点となります。
  • テストケースは全部で 30 個あります。各テストケースの得点の合計が、この問題の得点になります。

適切に指示を出すことで、得点を最大化してください。


入力

入力は以下の形式で標準入力から与えられます。入力はすべて整数です。

H W K T
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
:
A_K B_K C_K D_K
  • H はマップの行数を表す整数で、H=30 を満たします。
  • W はマップの列数を表す整数で、W=30 を満たします。
  • K はマップ上の車の数を表す整数で、K=450 を満たします。
  • T は車に出せる指示の回数の最大値を表す整数で、T=10,000 を満たします。
  • A_i および B_i は車 i の初期マス (A_i, B_i) を表す整数で、 1 \leq A_i \leq H, 1 \leq B_i \leq W を満たします。
  • C_i および D_i は車 i の目的マス (C_i, D_i) を表す整数で、 1 \leq C_i \leq H, 1 \leq D_i \leq W を満たします。
  • i \neq j ならば、(A_i, B_i) \neq (A_j, B_j) かつ (C_i, D_i) \neq (C_j, D_j) を満たします。

出力

出力は以下の形式で標準出力に出力してください。

L
movement_0
movement_1
:
movement_{L-1}
  • 1 行目に指示回数 L (0 \leq L \leq T) を出力してください。
  • t+2 (0 \leq t \lt L) 行目には、時刻tの時に各車へ出す指示を表す文字列movement_tを出力してください。
  • movement_t (0 \leq t \lt L)K 文字からなる文字列で、movement_ti 文字目は、車 i へ出す時刻 t での指示を表します。
  • 各指示は、以下の文字によって表されます。
    U
    現在のマスより1行小さいマスに移動します。(上に移動します)
    D
    現在のマスより1行大きいマスに移動します。(下に移動します)
    L
    現在のマスより1列小さいマスに移動します。(左に移動します)
    R
    現在のマスより1列大きいマスに移動します。(右に移動します)
    -
    移動しません。

テストケースの生成について

各テストケースは次の手順で生成されます。

  • 初期マスの候補となるK個のマスを、H \times W個のマスの中から、重複しないようにランダムに選ぶ。
  • それらの初期マスの候補を、ランダムに K 台の車に割り当てる。
  • 目的マスの候補となるK個のマスを、H \times W個のマスの中から、重複しないようにランダムに選ぶ。
  • それらの目的マスの候補を、ランダムに K 台の車に割り当てる。

入力例1

6 6 2 100
3 3 4 5
6 2 2 4

注意: この入力はテストケースとしての制約を満たしていません。

車1の初期マスを 1、車1の目的マスを X、車2の初期マスを 2、車2の目的マスを Y としたマップを以下に図示します。

出力例1

4
RR
RU
DU
-L

全ての指示を実行後のマップは以下のようになります。車1は目的マスに到着しています。

  • 時刻 0 では車1も車2も右に移動します。
  • 時刻 1 では車1は右に、車2は上に移動します。
  • 時刻 2 では車1は下に、車2は上に移動します。
  • 時刻 3 では車1は移動しません。車2は左に移動します。
  • この出力によって得られるスコアは、以下のように計算されます。
    • 車1の目的マスは (4,5) で、最終的な位置は (4,5) です。
    • 車2の目的マスは (2,4) で、最終的な位置は (4,2) です。
    • よって P_D20+ (|4-4|+|5-5|)+(|2-4|+|4-2|)=24 です。
    • P_T10 + 4 \times 0.01=10.04 です。
    • このテストケースでの得点は 10^7 / (24 \times 10.04) = 41500.6… を切り上げた 41501 となります。

入力例2

30 30 450 10000
12 11 24 29
17 16 6 26
29 8 25 18
11 27 28 19
16 16 24 28
27 17 6 12
4 11 14 28
27 21 9 12
21 10 26 26
24 20 11 12
16 23 12 15
3 21 11 9
7 2 22 30
20 18 18 7
4 29 22 1
7 13 12 19
4 17 21 10
23 10 27 29
6 29 21 21
17 22 10 7
12 9 13 25
18 24 8 10
15 29 22 29
8 15 1 23
1 18 11 7
17 28 30 25
25 26 12 7
9 7 15 18
17 3 3 8
18 20 11 5
20 1 25 13
18 8 16 4
4 5 15 22
2 13 24 24
7 30 6 28
10 16 2 14
19 7 9 17
13 26 5 24
10 25 30 6
4 12 26 15
30 16 25 14
24 4 6 5
24 13 12 26
24 21 5 1
20 27 1 24
6 7 17 20
22 3 10 19
18 15 12 23
7 24 6 10
3 23 27 12
16 27 1 7
17 13 16 15
18 10 2 29
10 9 8 27
9 1 19 29
16 13 17 6
25 16 7 1
18 6 12 17
26 14 20 16
2 9 9 13
22 2 16 16
12 28 15 17
11 5 25 2
11 29 8 21
25 9 17 27
5 19 4 9
13 29 22 25
30 28 11 20
9 5 1 2
6 11 21 30
22 13 22 20
6 28 19 6
11 24 5 15
29 24 5 14
21 29 25 10
18 21 14 6
2 8 17 30
6 16 26 8
9 30 11 26
11 7 20 23
18 19 6 6
16 4 27 4
7 22 8 28
2 4 5 6
30 20 4 11
15 5 9 18
12 21 30 23
20 25 18 14
8 11 9 28
8 17 26 11
30 9 30 29
14 11 24 15
17 6 4 17
4 23 14 26
18 7 14 12
29 10 9 22
20 22 17 18
26 23 17 8
23 16 7 16
3 16 22 28
16 15 27 19
8 3 29 2
28 21 16 5
19 19 13 17
2 30 12 25
28 23 13 16
6 24 6 19
8 22 24 22
20 29 10 16
7 26 27 9
1 21 2 24
25 30 1 30
17 23 28 16
10 13 23 29
19 14 25 11
16 11 6 29
13 2 4 1
20 4 9 27
11 15 2 15
22 26 10 23
23 7 11 1
6 17 3 2
18 14 16 13
24 28 1 13
8 30 26 29
9 24 8 7
21 30 25 26
26 11 9 29
21 14 30 8
28 17 28 12
3 5 28 13
21 22 21 7
30 13 24 6
24 10 15 4
28 16 5 18
24 11 18 24
24 12 1 17
20 11 3 7
30 29 17 17
12 5 19 10
19 24 30 27
29 3 1 10
4 3 21 22
15 16 17 16
1 28 6 4
30 6 23 14
12 26 4 23
6 25 23 12
4 26 25 9
13 22 29 16
19 20 6 22
4 14 12 4
17 14 4 12
13 7 20 8
29 12 15 27
2 25 22 6
12 3 28 3
7 18 19 20
18 9 13 24
10 11 8 19
29 25 9 4
11 3 20 28
14 24 11 23
19 8 25 6
14 10 1 29
9 29 28 4
16 5 27 3
10 12 2 9
9 19 7 23
15 18 10 1
6 27 13 21
4 30 30 2
1 1 28 5
24 2 14 15
29 19 12 3
12 22 14 14
25 28 9 30
15 8 11 11
15 14 19 11
19 10 29 26
21 21 2 22
24 1 11 28
30 30 8 1
28 5 26 3
4 8 19 27
6 30 11 3
19 15 22 5
16 28 5 29
2 5 23 9
26 25 25 19
17 5 7 22
18 1 3 19
28 14 6 1
10 21 8 13
14 28 18 26
9 8 16 24
11 25 4 4
28 11 24 13
30 3 24 9
3 9 6 30
16 20 3 3
11 9 23 4
15 6 12 16
13 23 12 24
25 19 28 1
5 24 27 28
28 10 26 25
27 20 15 2
17 20 21 14
3 6 19 3
17 11 21 6
1 29 2 4
25 17 29 15
22 24 12 30
22 27 6 23
6 19 30 19
13 16 30 28
14 1 6 18
27 16 6 3
8 26 9 26
18 4 23 13
16 30 14 1
20 6 10 6
12 24 3 10
19 1 24 16
5 11 7 2
2 20 29 8
18 2 16 1
4 24 22 8
17 8 27 16
19 22 24 27
22 28 9 23
1 10 12 10
12 4 3 13
8 1 11 24
3 7 13 9
21 3 1 12
30 1 26 6
1 16 13 8
10 17 24 20
6 9 5 21
22 21 5 5
10 20 16 27
5 18 18 16
16 12 23 26
25 22 12 6
29 27 6 17
15 19 23 30
2 3 25 27
5 28 8 3
15 20 12 9
15 4 25 7
9 12 7 4
24 30 25 4
20 5 3 5
6 2 20 25
15 23 23 28
26 26 7 25
23 27 27 2
5 27 30 12
21 1 26 13
23 24 10 11
5 29 3 6
2 19 5 11
22 7 5 19
20 17 27 26
14 23 25 22
21 15 19 30
28 19 1 27
27 30 25 5
23 17 14 7
27 5 17 2
26 30 29 5
7 12 14 21
9 3 15 3
8 24 19 28
3 3 7 11
2 26 10 26
30 10 21 11
1 3 22 23
10 28 2 7
19 27 14 24
28 24 30 13
21 9 14 2
15 28 2 23
5 6 10 13
27 18 16 2
17 18 10 28
19 11 20 26
13 11 16 21
15 25 24 3
3 24 22 24
1 8 11 15
15 15 23 2
26 15 29 1
1 14 20 15
28 1 4 20
7 10 3 11
14 5 25 1
29 11 13 26
25 29 8 5
18 27 17 3
22 14 25 16
17 7 19 8
25 23 30 1
23 23 12 13
26 24 10 17
8 4 12 8
17 30 7 24
29 2 20 10
7 1 3 23
26 9 29 23
23 15 30 7
27 9 15 21
25 4 1 25
8 14 23 17
23 12 19 7
13 27 27 14
5 15 27 17
16 22 10 21
1 4 3 27
12 29 21 2
24 15 29 17
21 8 23 18
12 17 30 18
28 20 11 17
23 18 21 27
13 5 5 4
14 2 6 24
1 12 28 10
14 27 18 25
27 4 30 26
16 2 7 28
5 20 28 8
3 17 20 9
1 25 21 16
26 19 11 30
4 20 25 8
10 15 20 17
6 5 19 26
20 14 24 5
1 7 21 9
13 15 30 15
23 2 7 8
15 1 1 18
19 17 10 18
16 10 21 15
23 21 6 14
8 25 1 1
21 18 13 18
9 4 24 11
18 28 17 1
27 3 25 24
20 9 10 15
30 11 13 11
13 28 29 14
17 25 23 1
15 12 16 10
19 18 13 23
1 19 2 6
8 7 8 30
22 12 6 7
8 2 16 9
17 26 7 26
3 30 14 19
4 4 28 27
13 12 20 1
9 6 15 13
24 24 2 28
21 20 26 17
29 29 25 28
23 28 30 9
16 21 29 18
22 15 27 27
5 12 20 13
26 7 11 8
12 7 13 2
16 25 15 9
20 20 13 6
16 3 21 17
8 27 17 11
18 12 12 5
4 18 9 2
1 2 28 30
15 17 18 6
17 24 26 5
16 9 20 12
30 14 22 4
19 5 21 8
12 15 9 10
6 8 2 20
25 2 6 27
30 7 13 5
6 26 16 29
10 30 7 12
9 28 23 16
3 13 30 11
27 19 30 17
1 5 9 16
10 3 14 11
19 30 8 4
3 10 2 21
1 15 8 16
29 4 18 13
6 12 28 15
7 27 24 26
26 10 7 6
12 8 14 4
4 16 5 2
13 18 21 19
26 18 3 16
24 7 6 20
3 15 19 23
20 16 19 16
14 6 27 30
13 30 1 28
14 30 20 11
23 29 8 11
9 2 1 5
27 25 30 4
18 3 22 9
8 10 21 4
7 20 30 22
14 20 16 20
22 29 5 20
24 19 12 20
28 13 11 16
21 7 12 29
21 5 14 8
12 19 1 3
10 4 15 23
2 11 14 18
25 25 15 28
22 9 13 30
27 6 9 15
15 13 25 30
25 13 16 23
7 29 10 10
17 9 28 23
11 1 19 14
21 13 12 18
27 2 6 21
20 30 23 21
11 14 20 7
26 8 4 28
5 16 15 25
18 26 7 19
22 1 19 19
20 12 4 8
7 7 3 14

ジェネレータに seed=1 を指定することで同じ入力が得られます。

出力例2

2
RRUL---UD--DR-LR---DD--RD-UD--R-D--UDLL-LRR-L-RR-LLDRRD-L---ULUL-U-U-D--LL---L-RLDRDL-DLDDU-UD---LU-D-RD-ULDU-R-DRLUUU-LLU-LLL-R----ULLUD--RRUD-DULDLDRD--UDDD-D-RRDU---UD-DDRL--RDDU-UL--DRR--UUU-R-URDL-RR-R-U-D-DRUUDRULDRU-LRLDU--RUD--RURDDRLDD-UU--------RRDLL---DRD-R-LUULD--LD--LL---D-RR---R-RDULL-UUD--LURLUU--RRD---U--R---ULRLD-LD-L---DLDDRRU-L----UUR-----RL--LDDDRLU-D-RU-L---U-DD--URLURU-LLD-R-URDRR-UD-DLRDURULR-DDLRURUU-RL-R--U-RLRD-U-LU-LD-R
DRU-DLDU-LUDRLLR-DDU-D-UL--D-L--DD--U-DDUURULDR-ULU-RURD--R-RL-L-D-L-D--LLD--LDD--DDLRR-DDD-R---U---D-LUDULDL-D--DR-UU-LUD-UR--RDLDLUU-DRULD-U--DUL--L-------DR-RRL-U-L-RU--DRLLRUUD-RLD--L-DLR--LLDURRR-DR--DRU-D--DRLUDR---U---LUUD-DUDRDRRR--RUDD--L-RL----U--UL-DL-LD--U-L--LR-DDD--LRDU-DD---D-RD-DRR-RL---LUUR--RD-URRUL-LRLD--U---DDRUD-L-DR--DLRU-R---ULRRL---LL-U--DDRD-DL----U--U-L-D-ULDU-L-RU-LR--RDU-DUD-RD-RU---LU-L----DD-----U-DR-R--D-U-ULL-DRR-U

ジェネレータとテスター

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

ジェネレータ・テスター


ビジュアライザ

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

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

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

ビジュアライザ


Submit提出する