No.540 Lattice Points and Paths
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
%20
tanzaku