문제1808--Symmetry

1808: Symmetry

실행시간 제한: 10 Sec  메모리사용 제한: 128 MB
제출: 80  통과: 34
[제출] [채점기록] [묻고답하기]

문제 설명

Farmer John loves symmetry and is currently arranging his cows on his field partitioned into an N x M (1 <= N <= 1,000,000,000; 1 <= M <= 1,000,000,000) grid.

To preserve symmetry, Farmer John places cows in the following way.
He puts a cow in the very center grid-square of the field; if no such grid-square exists, he simply stops. Then he partitions the field into four equal-sized smaller fields (separated by the row and column of the cow in the center) and arranges cows on each of those fields as before. He repeats the partitioning for ever-smaller fields until no center grid-square of a field exists or the field can not be subdivided.

By way of example, if N = 7 and M = 15 then Farmer John will place a cow in row 4, column 8 and arrange each of the resulting 3x7 fields. In each of the 3x7 fields, Farmer John will place a cow in row 2, column 4 and arrange each of the resulting 1x3 fields. The process is shown here (where C denotes a cow):

...............    ...............    .......|.......    .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 cows are required for this field. On the other hand, if N = M = 5 then Farmer John will only need to place one cow since the resulting 2x2 fields do not have center grid-squares. Help Farmer John determine how many cows he needs to arrange his field.

입력 설명

  • Line 1: Two space-separated integers: N and M

출력 설명

  • Line 1: The number of cows needed

입력 예시 Copy

7 15

출력 예시 Copy

21

출처/분류