A - 石油王Xの憂鬱

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N 個の石油タンクがあり、i (1 \leq i \leq N) 番目の石油タンクには C_i リットルまでの石油が入ります。はじめ、すべての石油タンクは空です。

石油を買いに、客が1人ずつやってきます。各客は、買いたい石油の量 D リットルと、待てる時間 T 分を提示します。D および T はランダムに決められます。

T 分以内に 1 つ以上の石油タンクを組み合せて、ちょうど D リットルの石油を用意すると、客は料金を D^2 だけ払ってくれます。石油を購入した客は帰り、すぐに新しい客が来ます。

石油を用意できずに T 分経ってしまうと、客は帰ってしまいます。その場合も、すぐに新しい客が来ます。

あなたは毎分、以下のいずれかの行動を実行しなければいけません。

  • fill i: i 番目の石油タンクに石油を満たします。すでに石油が満たされている場合は何も起こりません。
  • move i j: i 番目の石油タンクの石油を、j 番目の石油タンクに移します。i 番目の石油タンクに入っている石油が j 番目のタンクの空きよりも多い場合、 j 番目のタンクがいっぱいになるまで石油を入れ、入り切らなかった石油は i 番目のタンクに残ります。そうでなかった場合、i 番目の石油タンクに入っている石油を j 番目のタンクに全て移します。
  • change i: i 番目の石油タンクを、新しい空の石油タンクに交換します。もし石油が i 番目のタンクに残っていた場合、それは捨てられます。新しいタンクの容量 C_i はランダムに決められます。
  • pass: 今いる客に帰ってもらいます。すぐに新しい客が来ます。
  • sell n x_1 x_2 x_3 ... x_n: x_{1} 番目、x_{2} 番目、x_{3} 番目、… x_{n} 番目の n 個の石油タンクを売り渡します。このとき、n 個の石油タンクに含まれる石油の量の合計量は、ちょうど D でなければいけません。また、空のタンクを売り渡すことはできません。売り渡したタンクは、新しい空のタンクに交換されます。新しいタンクの容量 C_i はランダムに決められます。

これらの行動を 1000 回繰り返すことで、得られる料金の合計を最大化してください。

制約

  • N = 8
  • 1 \leq C_i \leq 10 (1 \leq i \leq N)
  • 1 \leq D \leq 50
  • 1 \leq T \leq 10
  • C_i (1 \leq i \leq N), D, T の値は整数であり、一様乱数によってランダムに決定されます。

入力

入力は以下の形式で標準入力から与えられます。入力は 1000 回与えられます。

D T
C_1 C_2 C_3 C_4 C_5 C_6 C_7 C_8
A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8
  • D は今いる客が買いたい石油の量であり、1 \leq D \leq 50 を満たします。
  • T は今いる客が待てる残り時間であり、1 \leq T \leq 10 を満たします。
  • C_i (1 \leq i \leq 8) は i 番目の石油タンクの容量であり、1 \leq C_i \leq 10 を満たします。
  • A_i (1 \leq i \leq 8) は i 番目の石油タンクに入っている石油の量であり、0 \leq A_i \leq C_i を満たします。また、最初は A_i=0 です。

出力

  • 出力は下記のフォーマットで標準出力に 1 行を出力してください。
  • 入力 1 回につき、必ず 1 回出力してください。
  • 1000 回の入出力を終えたら、プログラムを終了してください。
  • 出力の後には必ず改行し、flush してください。

i 番目の石油タンクに石油を満たす場合

fill i
  • 上記のフォーマットで、石油を満たす石油タンクの番号 i (1 \leq i \leq 8) を出力してください。

i 番目の石油タンクの石油を、j 番目の石油タンクに移す場合

move i j
  • 上記のフォーマットで、石油を移す元の石油タンクの番号 i (1 \leq i \leq 8) と石油を移す先の石油タンクの番号 j (1 \leq j \leq 8) を出力してください。この時、i と j は異なる整数でなければいけません。

i 番目の石油タンクを交換する場合

change i
  • 上記のフォーマットで、交換する石油タンクの番号 i (1 \leq i \leq 8) を出力してください。

今いる客に帰ってもらう場合

pass
  • pass とだけ出力してください。

石油を売り渡す場合

sell n x_1 x_2 ... x_n
  • 上記のフォーマットで、売り渡す石油タンクの数 n (1 \leq n \leq 8) を出力し、続いて売り渡す石油タンクの番号 x_i (1 \leq i \leq n, 1 \leq x_i \leq 8) を n 個出力してください。
  • A_i = 0 (1 \leq i \leq 8) の時、石油タンク i を売り渡す事はできません。
  • 同じ石油タンクの番号を 2 回以上出力することはできません。
  • 売り渡す石油タンクに含まれる石油の量の合計が、ちょうど D でなければいけません。

採点について

    各テストケースについて、得られた料金の合計が、そのテストケースの得点になります。

    テストケースは全部で 50 個あります。各テストケースの得点の合計値が、この問題の得点になります。

    フォーマットに違反した出力を行った場合や、1000回の入出力を行わずにプログラムが終了した場合の結果は定義されていません (WA とは限りません)。

入出力例

プログラムへの入力 プログラムの出力 説明 
3 2
6 2 3 2 9 10 7 7
0 0 0 0 0 0 0 0
客は 3 リットルだけ石油を買いたいです。また 2 分だけ待つことができます。最初、全ての石油タンクに入っている石油の量は 0 です。 
fill 1
1 番目の石油タンクに石油を満たします。 
3 1
6 2 3 2 9 10 7 7
6 0 0 0 0 0 0 0
1 番目の石油タンクが満たされました。また、1 分経過したため、客の待てる時間が 1 分減りました。 
move 1 4
1 番目のタンクの石油を 4 番目のタンクに移します。 
6 8
6 2 3 2 9 10 7 7
4 0 0 2 0 0 0 0
4 番目のタンクの容量は 2 なので、1 番目の石油タンクの石油のうち、2 リットルが 4 番目の石油タンクに移されました。また、客は待てる時間が 0 分になったため帰り、新しい客が来ました。新しい客は 6 リットル石油を買いたいです。また、8 分だけ待つことができます。 
sell 2 1 4
1 番目と 4 番目の 2 つのタンクを売り渡します。これによって 6 リットルの石油を売り渡したので、6^2=36 が料金として得られます。 
5 5
1 2 3 5 9 10 7 7
0 0 0 0 0 0 0 0
石油を買った客は帰り、新しい客が来ます。また、売り渡したタンクは新しい空のタンクに交換されます。 
change 2
2 番目のタンクを新しいタンクに交換します。 
5 4
1 1 3 5 9 10 7 7
0 0 0 0 0 0 0 0
2 番目のタンクが新しいものに交換されました。 
pass
今いる客に帰ってもらいます。 
8 2
1 1 3 5 9 10 7 7
0 0 0 0 0 0 0 0
前いた客は帰り、新しく 8 リットル石油が欲しい客が来ました。
... 入力は全部で 1000 回あります。各入力ごとに出力を flush する必要があります。

出力の flush について

この問題では、各入力ごとに、それに対する出力を flush する必要があります。主要な言語について、出力を flush する例を紹介します。どの例でも pass と出力して改行して flush しています。

C++

std::cout << "pass" << std::endl;

Java

System.out.println("pass");

Python 3.4

print("pass", flush=True)

テスター

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

テスター

B - 日本橋大渋滞

Time Limit: 4 sec / Memory Limit: 1024 MB

問題文

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

一番上の行を 1 行目、一番左の列を 1 列目とし、r 行 c 列にあるマスを (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_t の i 文字目は、車 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_D は 20+ (|4-4|+|5-5|)+(|2-4|+|4-2|)=24 です。
    • P_T は 10 + 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 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
  • このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

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

ビジュアライザ