TLE '16 Contest 4 P2 - Shepherding

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
ZQFMGB12
Problem type

You are shepherding near ancient Bethlehem when you hear that Jesus is born! Unfortunately, you are the last of your fellow shepherds to go and the K sheep that the shepherds are supposed to watch are still scattered around the field.

The field can be represented as an R meters by C meters grid where each square in the grid represents 1 m2 of grass. You have to herd the sheep into an area as small as possible, but each sheep needs to remain in the field and needs an entire square for itself. Afterward, you will erect a temporary fence around the sheep along the grid lines. What is the minimum length of fence, in meters, required?

Input Specification

The first line of input will contain two space separated integers, R and C (1 \le R, C \le 10^9).

The second line of input will contain a single integer, K (1 \le K \le R \cdot C).

For 20% of the points, 1 \le R, C \le 50.

For another 20% of the points, 1 \le R, C \le 1\,000.

For another 30% of the points, 1 \le R, C \le 10^6.

Note: It is recommended to use 64-bit integers to compute the solution (long long in C++, long in Java, int64 in Pascal).

Output Specification

Output a single integer, the minimum length of fence, in meters, required to surround the sheep.

Sample Input

5 5
14

Sample Output

16

Explanation for Sample Output

You can herd the sheep like this, where . represents an empty square and * represents a square with one sheep:

****.
****.
***..
***..
.....

This requires 4+4+3+2+1+2 = 16 meters of fencing.

Comments


  • 0
    Ken_Shi  commented on Dec. 23, 2016, 11:15 p.m. ← edited

    nvm


    • 0
      d  commented on Dec. 23, 2016, 11:52 p.m.

      This is the amount of fencing needed to surround the sheep. The fence starts at the top edge and goes counter-clockwise.