파일 업로드

대칭 교실

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

담임선생님인 형익은 대칭을 병적으로 좋아해서, 학급 자리 배치시간에 학생들을 N x M (1 <= N <= 1,000,000,000; 1 <= M <= 1,000,000,000) 그리드로 나누어진 교실에 배치하려고 합니다.

대칭을 유지하기 위해, 형익은 다음과 같은 방식으로 학생들을 배치합니다. 그는 가장 중심에 있는 그리드 칸에 학생을 배치합니다; 만약 해당하는 그리드 칸이 없다면, 그는 멈춥니다. 그 다음 그는 필드를 네 개의 동일한 크기의 작은 필드(중심에 있는 학생의 행과 열로 구분)로 나누고 각각의 그 필드에 학생을 그 전과 같은 방식으로 배치합니다. 그는 중심 그리드 칸이 존재하지 않거나 필드를 더 이상 나눌 수 없을 때까지 필드를 계속 분할합니다.

예를 들어, N = 7이고 M = 15라면 형익은 4번째 행, 8번째 열에 학생을 배치하고 결과적으로 나오는 3x7 필드를 각각 정리합니다. 각각의 3x7 필드에는 형익이 2번째 행, 4번째 열에 학생을 배치하고 난 후, 1x3 필드를 각각 정리하게 됩니다. 이 과정은 다음과 같이 표시됩니다 (여기서 S는 학생을 나타냅니다):

...............    ...............    .......|.......    .S.|.S.|.S.|.S.
...............    ...............    ...S...|...S...    ---S---|---S---
...............    ...............    .......|.......    .S.|.S.|.S.|.S.
............... -> .......S....... -> -------S------- -> -------S-------
...............    ...............    .......|.......    .S.|.S.|.S.|.S.
...............    ...............    ...S...|...S...    ---S---|---S---
...............    ...............    .......|.......    .S.|.S.|.S.|.S.

이 필드에는 21명의 학생이 필요합니다. 반면에, N = M = 5라면, 형익은 결과적으로 중심 그리드 칸이 없는 2x2 필드 때문에 한 명의 학생만 배치하면 됩니다. 형익이 그의 필드를 정리하는 데 필요한 학생의 수를 알아내는 것을 도와주세요.

💻 입력
  • 첫 번째 줄 : 공백으로 구분된 두 개의 정수: N과 M
🖨️ 출력
  • 첫 번째 줄 : 필요한 학생의 수

💻 예제 입력 1
7 15
🖨️ 예제 출력 1
21

출처: USACO 2011 January Bronze 1