問題一覧 > 教育的問題

No.8008 The Mesh Pattern of a Certain Mayonnaise

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 44
作問者 : butchi_y
お気に入りにしたユーザー ProblemId : 235 / 自分の提出
問題文最終更新日: 2026-06-27 04:05:49
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

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もしくは右上の雲マークをクリックしてアカウントを作成してください。