AutomaticVacuumCleaner | Topcoder Archive

Problem Statement

An automatic vacuum cleaner is cleaning a rectangular room. The floor of the room is divided into a grid of unit squares with R rows by C columns.

The robot starts in the top left corner. When cleaning the room, the robot cleans one square at a time, and it proceeds along the room in a zig-zag fashion: first, it cleans the entire first row from left to right, then the entire second row from right to left, then the third row from left to right again, and so on. Here is the order in which the robot would clean a room with R=5 and C=6:

 1  2  3  4  5  6
12 11 10  9  8  7
13 14 15 16 17 18
24 23 22 21 20 19
25 26 27 28 29 30

Note that the robot always moves from a cell to another cell that shares a side with the previous one. Such a movement will be called a move.

The robot just executed the following program:

Move to the top left corner.
Clean the first A cells, and remember the last cell you cleaned.
Clean another B cells (still continuing the pattern defined above).
Using as few moves as possible, return to the cell you remembered in step 2.

You are given the longs R, C, A, and B. Compute and return the number of moves the robot made in step 4 of the above program.

Definition

Class:: AutomaticVacuumCleaner
Method:: getDistance
Parameters:: long, long, long, long
Returns:: long
Method signature:: long getDistance(long R, long C, long A, long B)
(be sure your method is public)

Constraints

R will be between 1 and 10^18, inclusive.
C will be between 1 and 10^18, inclusive.
A will be between 1 and 10^18, inclusive.
B will be between 0 and 10^18, inclusive.
A+B will not exceed R*C

Examples

```
5
```
```
6
```
```
2
```
```
2
```
```
Returns: 2
```
After step 2 the robot remembered the cell marked "2" in the example shown above. After step 3 (i.e., after cleaning two more cells) the robot was in cell "4". To get back to cell "2", it made two moves to the left.
```
5
```
```
6
```
```
9
```
```
5
```
```
Returns: 3
```
The robot needs three moves to get from cell labeled 14 to cell labeled 9 in the figure shown above.
```
5
```
```
6
```
```
9
```
```
0
```
```
Returns: 0
```
Note that B may be zero. As the robot made no moves in step 3, it doesn't need any moves in step 4 either.
```
500
```
```
1
```
```
30
```
```
450
```
```
Returns: 450
```

287624057338675345

442885325636476446

284187065224529461

28160580732616308

Returns: 28160580732616308

Watch out for integer overflow.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.