No.540 格子点と経路
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 : %20 / テスター : tanzaku
タグ : / 解いたユーザー数 14
作問者 : %20 / テスター : tanzaku
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。