A - ツカモの栽培

Contest Duration: 2018-03-03(Sat) 01:30 - 2018-03-03(Sat) 09:30 (local time) (480 minutes) Back to Home

A - ツカモの栽培 Editorial

Time Limit: 6 sec / Memory Limit: 256 MB

配点 : $50000000$ 点

問題文

高橋君は、新たな惑星を発見しました。この惑星では、植物「ツカモ」がよく育つことが分かっています。ツカモを出来るだけ多く育てましょう！

この惑星は、 $50×50$ のマス目で表されます。左から $x$ 番目、上から $y$ 番目のマスが $(x,y)$ です。左上のマスが $(1,1)$ 、右上のマスが $(50,1)$ 、右下のマスが $(50,50)$ です。マスは、以下の $5$ 種類で構成されています。

更地：何もない土地です。ツカモが生えると畑になります。
畑：ツカモが生えている土地です。ツカモは、 $1$ 本から $99$ 本生えています。
岩：岩です。これがあるとツカモの繁殖が出来ず、また、移動コストも大きくなります。
ワープゲート：高橋君が、地球からこの惑星に来る時に使います。最初は必ず $1$ つだけ存在します。
道路：ワープゲートから、高橋君が移動するために使う道です。移動コストが小さいです。

高橋君は、 $2$ つのパラメータを持っています。

お金：　道路やワープゲートの作成、更地化、労働力のアップに使います。収穫とアルバイトで増えます。初期値は $100$ です。お金は次のターンに引き継がれます。
労働力：高橋君が一度にツカモを収穫できる量の計算に使います。初期値は $100$ で、労働力のアップで増やすことが可能です。労働力を消費しても、次のターンには回復します。

ツカモは、以下のような特性を持っています。

ツカモが同じマスに $100$ 本揃った瞬間、そのマスのツカモは全て岩になる。
あるマスについて、そのマスが更地もしくは畑であり、そのマス自身か上下左右に隣り合うマスが畑である場合、そのマスの次のターンのツカモは $1$ 本増加する。岩はツカモに含めない。

高橋君には、 $1000$ ターンの開発期間が与えられます。この $1000$ ターンの間に、出来るだけ多くのツカモを収穫したいです。高橋君の $1000$ ターンの出力をしてください。高橋君が出来る行動は、以下の $7$ つのうち、どれか $1$ つです。

道路の作成Copy

Copy

road  $X_1$   $Y_1$   $X_2$   $Y_2$

上下または左右の直線に道路を作る。 $X_1=X_2$ または $Y_1=Y_2$ を満たす必要があり、満たさない場合は WA となる。岩やワープゲートが間にあるとそこには道路が出来ないが、畑は道路となり、畑にあるツカモは破棄される。道路の作成には、長さの $2$ 乗分のお金がかかる。岩やワープゲートや道路も長さに含まれる。お金が払えない場合は、道路は作成されない。

ツカモを植えるCopy

Copy

plant  $X$   $Y$

更地か畑のマスのツカモを $1$ 増やす。更地・畑以外のマスだった場合は無視される。

収穫Copy

Copy

harvest  $X_1$   $Y_1$   $X_2$   $Y_2$

長方形の範囲を指定してツカモを収穫する。収穫は左上のマスから順番に行われる。畑以外のマスは無視され、労働力を消費しない。あるマスのツカモの収穫には、 $(そのマスへの移動距離 - 10)$ だけの労働力を消費する。労働力が足りないマスは無視される。ツカモが収穫されたマスは更地になる。ツカモを収穫すると、一本につき１円が得られる。（移動距離については後述）

更地化Copy

Copy

destroy  $X_1$   $Y_1$   $X_2$   $Y_2$

区間を指定して左上から順番に全て更地にする。道路・岩・畑は全て更地になるが、ワープゲートは無視され、お金を消費しない。左上から順番に更地化していく。マス１つ１つに対し、そのマスへの移動距離と同じだけお金がかかる。お金が足りない場合は何も行われない。元々更地の場合は無視される。（移動距離については後述）

労働力のアップCopy

Copy

growup  $A$

お金を使って労働力を $A$ 増やす。労働力の初期値は $100$ で、労働力を $A$ 増やすのに、 $A*A$ 円かかる。お金が足りない場合は、増やすことが可能な最大値が自動的に選択される。

ワープゲート作成Copy

Copy

warpgate  $X$   $Y$

マス $(X,Y)$ にワープゲートを建築する。お金が $1000$ かかる。指定したマスが更地、畑、道路以外の場合は無視され、お金もかからない。

アルバイトCopy

Copy

work

お金が $1$ 増える。

移動距離の計算方法について

更地化、収穫の計算に使われる移動距離は、そのターンの開始時における、ワープゲートからそのマスへの最短経路で計算されます。ワープゾーンを移動距離 $0$ として、そこから上下左右の各マスに移動できます。各マスに移動するためのコストは、移動するマスが道路だった場合は $1$ 、岩だった場合は $50$ 、その他の場合は $10$ かかります。

区間の指定についてCopy

Copy

 $X_1$   $Y_1$   $X_2$   $Y_2$

上記の指定があった場合、マス $(X_1, Y_1)$ とマス $(X_2, Y_2)$ を端点とした、長方形領域に対して処理を行います。 $X_1 ≦ X_2$ および $Y_1 ≦ Y_2$ を満たす必要があります。左上から順番に処理を行い、コストが足りないマスについては無視されます。上にあるマスほど優先され、 $Y$ 座標が同じ場合は、左にあるマスほど優先されます。

各ターンの進行について

各ターンは、以下の順番で進行します。

高橋君の行動の反映
ツカモの成長

例えば、plantコマンドでツカモを植えた時、植えた後にツカモが成長するため、次のターンでそのマスのツカモは $2$ に増加していることなどに注意してください。

行動まとめ

行動をまとめると以下のようになります。なお、「お金」もしくは「労働力」をまとめて「コスト」と表現しています。

行動まとめ表

各ターンの進行

制約

$N = 50$
入力は、各マスに対し、 $15パーセント$ が岩、残りは更地になるようにランダムで生成される。その後、マスの $1$ つをランダムに選び、そのマスをワープゲートとする。

入力

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

 $A_{1,1}$  $A_{1,2}$  ...  $A_{1,N}$ 
 $A_{2,1}$  $A_{2,2}$  ...  $A_{2,N}$ 
:
 $A_{N,1}$  $A_{N,2}$ 　...  $A_{N,N}$

$A_{y,x}$ は、マス $(x,y)$ の初期状態を表し、.が更地、#が岩、Wがワープゲートを表す。

出力

毎ターンの高橋君の行動を、 $1000$ 行で出力せよ。各行動は、コマンド座標指定 の順で行う。各コマンドの出力方法については、各行動についての記述に従う。

採点方法

$1$ つのテストケースごとに、ツカモの収穫数が個別スコアとなります。

$50$ つのテストケースの個別スコアの総和が、そのプログラムのスコアになります。

なお、 $1$ ケースでも、出力の正しくない提出があった場合、example以外の点数は全て $0$ 点となります。

入力例

入力ファイルはこちらから(zip)

採点結果の「example_01」「example_02」「example_03」が、こちらのデータとなります。このデータも採点対象となります。

決勝上位5名のexample_01に対する出力ファイルはこちらから(zip)

ビジュアライザー

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

このビジュアライザはchromeでの使用を推奨します。他の環境で正常に動作することを保証していません。特にInternet Explorerでは動作しないことを確認しています。
このビジュアライザから解答の提出はできません。 AtCoder 上で解答を提出して下さい。
このビジュアライザ上で計算された点数は、当コンテスト上での点数を保証するものではありません。このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

入力ファイル：　　

出力ファイル：　　

Score

ツカモ

おかね

100

労働力

100 / 100