moner_ari   1년 전

[문제]

농부 존은 '대칭'을 너무나 좋아한 나머지, N x M (1 <= N <= 1,000,000,000; 1 <= M <= 1,000,000,000) 크기의 격자로 나누어진 그의 들판에 소를 배치시키고 있습니다.

'대칭성'을 지키기 위해, 농부 존은 소를 다음과 같이 배치합니다. 그는 소 1마리를 들판의 가장 가운데 격자 칸에 놓습니다. 만약 그런 격자 칸이 없다면, 그는 소를 놓는 것을 그만둡니다. (만약 그런 격자 칸이 있다면), 그는 들판을 동일한 크기의 작은 들판 4개로 들판을 분할하고 (한가운데에 있는 소의 행과 열을 기준으로 분할합니다.) 이전과 같이 들판 4개에 소를 놓습니다. 이런 식으로, 더 이상 들판의 한가운데 격자 칸이 존재할 수 없거나, 들판이 더 이상 분할될 수 없을 때까지 계속 들판을 분할하고 소를 놓는 것을 반복합니다.

예를 들어, N = 7, M = 15라면, 농부 존은 소 1마리를 4번째 행, 8번째 열에 놓으며, 각 들판을 3x7 크기의 작은 들판으로 나눕니다. 각각의 3x7 들판에, 농부 존은 소 1마리를 2번째 행, 4번째 열에 놓으며, 각 들판을 다시 1x3 크기의 더 작은 들판으로 나눕니다. 이러한 과정을 나타내면 아래와 같습니다: (이때 C는 소를 의미합니다)

...............    ...............    .......|.......    .C.|.C.|.C.|.C.
...............    ...............    ...C...|...C...    ---C---|---C---
...............    ...............    .......|.......    .C.|.C.|.C.|.C.
............... -> .......C....... -> -------C------- -> -------C-------
...............    ...............    .......|.......    .C.|.C.|.C.|.C.
...............    ...............    ...C...|...C...    ---C---|---C---
...............    ...............    .......|.......    .C.|.C.|.C.|.C.

이 들판에는 21마리의 소가 있어야 합니다. 한편, N = M = 5인 경우에는, 농부 존은 소를 1마리만 놓으면 되는데, 소를 놓은 후 얻은 2x2 들판에는 정확히 가운데 격자 칸이 없기 때문입니다. 농부 존을 도와 그가 들판에 놓아야 하는 소의 수를 구하세요.

--------

[입력]

1번째 줄에 띄어쓰기로 구분된 2개의 정수 N, M이 주어집니다.

--------

[출력]

1번째 줄에 필요한 소의 수를 출력합니다.

댓글을 작성하려면 로그인해야 합니다.