問題一覧 > 通常問題

No.540 Lattice Points and Paths

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 14
作問者 : %20 / テスター : tanzaku
お気に入りにしたユーザー ProblemId : 1509 / 自分の提出
問題文最終更新日: 2020-03-18 00:43:16
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 168 (順位表) の他の問題:

Note

The intended solution is believed to be correct, but it has not been rigorously proven. We are looking for someone to prove it, for example on a blog. → It has been proven by maspy.

Problem Statement

Among paths satisfying all of the following conditions, find the maximum number of line segments that a path has.

  • The path passes exactly $1$ time through every lattice point contained in the region (including its boundary) enclosed by the $4$ points $(0,0),(W,0),(W,H),(0,H)$ on the $xy$-plane.
  • The path does not pass through any point outside the enclosed region.
  • The path only connects lattice points that are horizontally or vertically adjacent.
  • The path is not a cycle.

A line segment of a path means "a section of the path over which it keeps moving in the same direction". A point is not a line segment.
A lattice point means "a point whose $x$-coordinate and $y$-coordinate are both integers".
Horizontally adjacent lattice points means "lattice points such that, between the $2$ points, the absolute difference of the $x$-coordinates is exactly $1$ and the $y$-coordinates are equal".
Vertically adjacent lattice points means "lattice points such that, between the $2$ points, the absolute difference of the $y$-coordinates is exactly $1$ and the $x$-coordinates are equal".

Input

$W$ $H$

The input satisfies the following constraints.

  • $0\le W,H\le 10^{5}$
  • $W,H$ are both integers.

Output

Output the maximum number of line segments that the path has. Print a newline at the end.

Sample

Sample 1
Input
2 2
Output
6

For example, taking the path shown in the figure below gives $6$ line segments, which is the maximum.

Sample 2
Input
5 3
Output
21

Sample 3
Input
1234 5678
Output
7007887

Sample 4
Input
0 0
Output
0

In this case, the path consists only of a single point that is both its start and its end, so no line segment is formed.

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