Hide

Problem F
不合理な分割

/problems/irrationaldivision/file/statement/ja/img-0001.png
The example game described in the problem statement.
あなたの家族はチョコレートに恵まれている!巨大なチョコレートを、あなたと妹とで分けるよう与えられた。しかし、前回にはあなたが多く取ったので、両親は公平に分けるため(そして、他のチョコレートを隠してしまう時間を稼ぐため)のゲームを考えた。 興味深いことに、両親は長方形のピースからなるチョコレートを与えた。それは、ダークチョコレートとホワイトチョコレートがチェス盤のように並んでいる。 あなたと妹はダークチョコレートは好きだが、ホワイトチョコレートは嫌い!なので、二人はダークチョコレートをできるだけ多く、一方ホワイトチョコレートはできるだけ少なくしようと考えている。ダークチョコレートを1マス得るごとに、幸福を1単位得ることができ、ホワイトチョコレートを1マス得るごとに、幸福を1単位失う。(妹も同様です) あなたは妹がとても好きだが、兄弟の間には常に熾烈な競争が横たわっているので、あなたの目的は自分の得た幸福と妹の得た幸福の差を最大にすることだ。(もちろん、妹も同様に考えている) ゲームは以下のように進む。

両親は $p \times q$ マスの長方形の前述のチョコレートをテーブルに置いた。あなたはテーブルの西側、妹は南側に座っている。$p$ は南北方向の長さで、$q$ は東西方向の長さだ。また、北西のマスはダークチョコレートだ。 そして、あなたから順に手番を行い、チョコレートを分割し、自分の側にあるチョコレートを手に入れる。あなたは西側から任意の列数で分割することができる。同様に、妹は南側から任意の行数で分割することができる。これを繰り返し、チョコレートがなくなるまで続ける。 妹はとても賢いので、常に最善手を行う。

ゲームは、例えば以下のように進む。あなたと妹は $3\times 4$ マスのチョコレートから開始した。あなたは $2$ 列取得する。そこには、$3$ マスのダークチョコレートと$3$ マスのホワイトチョコレートが含まれるため、合計で幸福は0になる。妹は $1$ 行取得する。そこには1マスのダークチョコレートと1マスのホワイトチョコレートが含まれるため、妹も幸福は0になる。次にあなたは1列取得し、やはり幸福は得られない。そして妹が $1$ 行取得すると、彼女が $1$ 幸福得る!最後にあなたが最後のマスを得て、$1$ 幸福失い、最終的な得点は $-1 - 1 = -2$ となる。この様子は図を参照。(注: 今回の戦略は最適ではない)

入力

入力は $p$$q$$2$つの整数で、いずれも最大$100$。チョコレートの高さと幅を表す。

出力

あなたの得られる最大の得点、すなわち、あなたの幸福の合計と妹の幸福の合計との差異。

サンプル入力 1 サンプル出力 1
1 2
2
サンプル入力 2 サンプル出力 2
2 2
0
サンプル入力 3 サンプル出力 3
4 3
0

Please log in to submit a solution to this problem

Log in