A - 石油王Xの憂鬱 Editorial /

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)

テスター

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

テスター