No.8008 The Mesh Pattern of a Certain Mayonnaise
タグ : / 解いたユーザー数 44
作問者 :
butchi_y
Note
This problem and its intended solution are based on my expectation that they are probably correct, and I have not been able to prove them.In other words, this is a problem that is seeking a proof. Thank you in advance.
Problem Statement
This problem is about the mesh pattern printed on the bag of a certain mayonnaise.
Reference image of a certain mayonnaise (external site)
Suppose this mesh pattern is composed of $N$ blocks vertically $\times$ $M$ blocks horizontally.
Find the minimum number of strokes needed to draw this mesh pattern using only line segments that do not turn at intersections.
If possible, please provide an explanation as well.
Input
N M
- All inputs are given as integers.
- $1 \le N \le 1000000=10^6$
- $1 \le M \le 1000000=10^6$
Output
Output the minimum number of strokes needed to draw the pattern. Print a newline at the end.
Sample
Sample 1
Input
2 2
Output
2
For this figure, using line segments that do not turn at intersections, at least $2$ strokes are needed.
Sample 2
Input
2 3
Output
1
For this figure, it can be drawn in $1$ stroke using line segments that do not turn at intersections.
Sample 3
Input
4 4
Output
4
For this figure, it seems that as many as $4$ strokes are needed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。