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
128654
56300
398384431
Returns: 0
6
5
2507971
Returns: 3155
27356
15909
234
Returns: 0
49911
94494
390160982005
Returns: 1104851
85092
1193
24
Returns: 0
6
2771
1500396267
Returns: 74691
306
432
10275110721
Returns: 201993
247443
1
76123533
Returns: 306
71002
348
7883720804
Returns: 106229
8148
21
858
Returns: 0
5
14
133
Returns: 3
51
12
42677
Returns: 349
3
519151
5347748357
Returns: 10297
6
19
15457231292
Returns: 248628
9690
103
55885287
Returns: 5663
75
93141
371828
Returns: 0
1003
1
257000819
Returns: 31057
102
171
224588210
Returns: 29698
50010
2791
1082666476662
Returns: 2028223
31513
3677
1
Returns: 0
28
1
4102225513
Returns: 128067
58
20
3577967715
Returns: 119553
96
4047
59268
Returns: 0
1240
44775
41
Returns: 0
40
5
42830565591
Returns: 413864
2
120
163741473429
Returns: 809176
13
3722
2093771255
Returns: 87779
4312
679
300202
Returns: 0
12
4
110712
Returns: 648
5857
359
286978148
Returns: 27663
838425
71486
137060528901
Returns: 91987
25250
3
7514
Returns: 0
31
147942
1443
Returns: 0
30215
265257
131
Returns: 0
93454
13638
36127049
Returns: 0
3
11
8604368869
Returns: 185504
4831
234731
5789029456
Returns: 19831
25
15
973634708
Returns: 62365
120641
3259
2
Returns: 0
1
896
34339595178
Returns: 369720
84877
17
155169726072
Returns: 702936
2
160
871642702213
Returns: 1867073
1322
20227
803
Returns: 0
1
937922
17970303
Returns: 18
77
1
5536424
Returns: 4626
198221
180
2992
Returns: 0
390959
881
165
Returns: 0
2979
35441
14770356
Returns: 0
4055
81
8354325911
Returns: 178667
233175
193
40191032205
Returns: 172170
107586
165
228751816950
Returns: 848808
155889
371196
6
Returns: 0
28
2
117
Returns: 2
755318
45
19309
Returns: 0
854970
52
764351578
Returns: 842
150
921689
73317
Returns: 0
24
429136
201003968
Returns: 444
6056
4
436407599404
Returns: 1315162
6908
2691
2471896869
Returns: 89836
7
311397
3309182561
Returns: 10619
0
0
12345678902
Returns: 222221
0
0
9876654321
Returns: 198761
0
89789
23263466747
Returns: 215257
0
1000000
100000000000000
Returns: 18999998
1
1
100000000000000
Returns: 19999996
0
0
100000000000000
Returns: 19999998
4
0
7
Returns: 1
4
0
53
Returns: 9
0
0
100
Returns: 18
3
7
1000
Returns: 52
1000000
0
10000000000
Returns: 9999
2
1
6
Returns: 0
0
0
1000000000000
Returns: 1999998
0
1
3
Returns: 1
1000000
1000000
1
Returns: 0
5
0
13
Returns: 2
0
0
10000
Returns: 198
3
5
100
Returns: 10
0
0
4
Returns: 2
42
13
100000000000000
Returns: 19999943
434
347
12334345
Returns: 6242
0
0
2
Returns: 1
0
999999
1000000
Returns: 0
1000000
1000000
10000000000
Returns: 0
50857
62382
4967702679996
Returns: 4344428
31812
27010
1000027788
Returns: 4424
99998
99996
9999600001
Returns: 0
1
100
300
Returns: 1
129678
13429
1801648341
Returns: 464
1000000
1000000
1000000000000
Returns: 0