DivideThePlane | Topcoder Archive

Problem Statement

You have a two-dimensional plane. You have already drawn some lines onto the plane: exactly H distinct horizontal lines and exactly V distinct vertical lines.

The lines can be seen as region boundaries. You want to divide your plane into at least N regions. If necessary, you can draw additional straight lines. Each of the new lines must also be either horizontal or vertical.

Compute and return the minimum number of additional lines you need.

Definition

Class:: DivideThePlane
Method:: makeCuts
Parameters:: int, int, long
Returns:: long
Method signature:: long makeCuts(int H, int V, long N)
(be sure your method is public)

Constraints

H will be between 0 and 10^6, inclusive.
V will be between 0 and 10^6, inclusive.
N will be between 1 and 10^14, inclusive.

Examples

```
0
```
```
0
```
```
1
```
```
Returns: 0
```
You don't have any lines drawn yet. You want to have at least one region. Luckily, the whole plane is now one region and that's exactly what you need, so you do not have to draw any lines.
```
0
```
```
0
```
```
3
```
```
Returns: 2
```
If you draw a single line, you will have two regions, which isn't enough. Thus, you need at least two lines. Drawing two lines is clearly sufficient. We can draw two parallel lines and get three regions, or we can draw two perpendicular lines and get four regions. Both of these ways are valid optimal solutions for this test case.
```
4
```
```
0
```
```
3
```
```
Returns: 0
```
You already have four horizontal lines. These already divide the plane into five regions, so you have enough regions and you do not have to draw any more lines.
```
4
```
```
0
```
```
20
```
```
Returns: 3
```
The only optimal solution here is to draw three vertical lines. This will produce exactly 20 regions. The plane will look as follows: | | | | | | ----+--+--+---- | | | ----+--+--+---- | | | ----+--+--+---- | | | ----+--+--+---- | | | | | | and here are the individual regions numbered: | | | 1| 2| 3| 4 ----+--+--+---- 5| 6| 7| 8 ----+--+--+---- 9|10|11|12 ----+--+--+---- 13|14|15|16 ----+--+--+---- 17|18|19|20 | | |
```
1
```
```
3
```
```
35
```
```
Returns: 6
```
One of the multiple optimal solutions is to add five new horizontal lines and one new vertical line (so there will be a total of six horizontal and four vertical lines). Another optimal solution is to add four horizontal and two vertical lines. In either case the total number of new lines is six.
```
99999
```
```
99997
```
```
10000000000
```
```
Returns: 2
```
Watch out for integer overflow.
```
4
```
```
7
```
```
12345
```
```
Returns: 210
```

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.