Problem F
不合理な分割
Languages
en
ja
両親は $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 |