問題一覧 > 通常問題

No.540 格子点と経路

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 13
作問者 : %20%20 / テスター : tanzakutanzaku
0 ProblemId : 1509 / 出題時の順位表
問題文最終更新日: 2020-03-18 00:43:16

Note

想定解は正しいと思われますが、正確な証明はされていません。ブログなどで証明される方募集中です。 → maspy さんによって証明されました。

問題文

次の条件をすべて満たすような経路について、その経路のもつ線分の個数の最大値を求めてください。

  • $xy$ 平面上の $4$ 点 $(0,0),(W,0),(W,H),(0,H)$ によって囲まれる領域(境界線を含む)に含まれるすべての格子点をちょうど $1$ 回ずつ通る。
  • 囲まれる領域外の点は通らない。
  • 横または縦に隣り合った格子点同士のみを結ぶように通る。
  • 閉路でない。

経路のもつ線分とは、「経路上を同一の方向に進み続けている区間」を指します。点は線分ではありません。
格子点とは、「 $x$ 座標、$y$ 座標がともに整数であるような点」を指します。
横に隣り合った格子点同士とは、「 $2$ 点間の $x$ 座標の差の絶対値がちょうど $1$ で $y$ 座標が等しい格子点同士」を指します。
縦に隣り合った格子点同士とは、「 $2$ 点間の $y$ 座標の差の絶対値がちょうど $1$ で $x$ 座標が等しい格子点同士」を指します。

入力

$W$ $H$

入力は以下の制約を満たします。

  • $0\le W,H\le 10^{5}$
  • $W,H$ はいずれも整数である。

出力

経路のもつ線分の個数の最大値を出力してください。最後に改行してください。

サンプル

サンプル1
入力
2 2
出力
6

例えば、下図のような経路を通ると、線分の個数は $6$ になり、これが最大値となります。

サンプル2
入力
5 3
出力
21

サンプル3
入力
1234 5678
出力
7007887

サンプル4
入力
0 0
出力
0

この場合、経路は始点かつ終点であるような点のみになり、線分はできません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。