No.540 格子点と経路
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 :
%20
/ テスター :
tanzaku
タグ : / 解いたユーザー数 14
作問者 :


問題文最終更新日: 2020-03-18 00:43:16
Note
想定解は正しいと思われますが、正確な証明はされていません。ブログなどで証明される方募集中です。 → maspy さんによって証明されました。
問題文
次の条件をすべて満たすような経路について、その経路のもつ線分の個数の最大値を求めてください。
平面上の 点 によって囲まれる領域(境界線を含む)に含まれるすべての格子点をちょうど 回ずつ通る。- 囲まれる領域外の点は通らない。
- 横または縦に隣り合った格子点同士のみを結ぶように通る。
- 閉路でない。
経路のもつ線分とは、「経路上を同一の方向に進み続けている区間」を指します。点は線分ではありません。
格子点とは、「
横に隣り合った格子点同士とは、「
縦に隣り合った格子点同士とは、「
入力
入力は以下の制約を満たします。
はいずれも整数である。
出力
経路のもつ線分の個数の最大値を出力してください。最後に改行してください。
サンプル
サンプル1
入力
2 2
出力
6
例えば、下図のような経路を通ると、線分の個数は
サンプル2
入力
5 3
出力
21
サンプル3
入力
1234 5678
出力
7007887
サンプル4
入力
0 0
出力
0
この場合、経路は始点かつ終点であるような点のみになり、線分はできません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。