실행 시간 제한 | 메모리 제한 |
---|---|
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 필드 때문에 한 명의 학생만 배치하면 됩니다. 형익이 그의 필드를 정리하는 데 필요한 학생의 수를 알아내는 것을 도와주세요.
7 15
21