Connection Status:
Competition Arena > AutomaticVacuumCleaner

AutomaticVacuumCleaner

TCO18 India Fun · 2018-04-20 · by misof

TCO18 India Fun · 2018-04-20 · by misof · Simple Math
Class Name: AutomaticVacuumCleaner
Return Type: long
Method Name: getDistance
Arg Types: (long long, long long, long long, long long)
Problem Statement

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:

  1. Move to the top left corner.
  2. Clean the first A cells, and remember the last cell you cleaned.
  3. Clean another B cells (still continuing the pattern defined above).
  4. 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.

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
0)
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.

1)
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.

2)
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.

3)
1
1
1
0
Returns: 0
4)
2
2
1
0
Returns: 0
67)
287624057338675345
442885325636476446
284187065224529461
28160580732616308
Returns: 28160580732616308

Watch out for integer overflow.

Submissions are judged against all 106 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AutomaticVacuumCleaner with a public method long long getDistance(long long R, long long C, long long A, long long B) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous