题目描述

Description

Mr. Bender has a digital table of size n × n, each cell can be switched on or off. He wants the field to have at least c switched on squares. When this condition is fulfilled, Mr Bender will be happy.

We’ll consider the table rows numbered from top to bottom from 1 to n, and the columns — numbered from left to right from 1 to n. Initially there is exactly one switched on cell with coordinates (x, y) (x is the row number, y is the column number), and all other cells are switched off. Then each second we switch on the cells that are off but have the side-adjacent cells that are on.

For a cell with coordinates (x, y) the side-adjacent cells are cells with coordinates (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1).

In how many seconds will Mr. Bender get happy?

Input

The first line contains four space-separated integers n, x, y, c (1 ≤ n, c ≤ 10^9; 1 ≤ x, y ≤ n; c ≤ n^2).

Output

In a single line print a single integer — the answer to the problem.

Sample test(s)

input
6 4 3 1

output
0

input
9 3 8 10

output
2

Note

Initially the first test has one painted cell, so the answer is 0. In the second test all events will go as is shown on the figure.

题目链接

http://codeforces.com/problemset/problem/255/C

解题思路

题目大意：给一个n * n的格子，然后给一个坐标(x, y)，从这个格子开始，每隔1秒格子会向四周扩散，问经过多少秒格子的总数会大于等于给定的c。
解题思路：由于n非常的大，所以无法开数组进行模拟；又因为在扩散的时候碰到墙壁的话，不会再继续向墙的方向进行扩散了，所以公式的解法也行不通。因此我们就需要通过数学来计算一定时间内格子的数目，转换为面积的计算，这样就容易了很多。

因此我们可以二分所有可能的时间，来计算最终的结果。二分的下限是0，上限是n * 2。在计算格子的数量的时候，我们需要做比较多的判断。首先需要先计算出在一定时间内，不考虑墙壁影响的情况下的格子数量，然后判断是否碰到了四周的墙壁，碰到了就减去超出的部分。另外注意如下类似的情况：如果同时超出了左侧墙壁和上侧墙壁，那么我们在分别处理上侧和左侧的时候会有重复的部分，因此我们要把多减掉的部分再加回来。其他三个角亦是如此。

代码写得应该比较清晰，画一下图就可以理解了。

AC代码

4 KB/30 ms/GNU G++ 4.9.2

#include <cstdio>
typedef long long ll;
using namespace std;

ll l, r, u, d;
ll n, x, y, c;
ll sqr(ll x)
{
    return x * x;
}

ll tri(ll x)
{
    return (x + 1) * x / 2;
}

bool solve(ll t)
{
    ll sum = t * t + (t + 1) * (t + 1);
    if (t > l) sum -= sqr(t - l);
    if (t > r) sum -= sqr(t - r);
    if (t > u) sum -= sqr(t - u);
    if (t > d) sum -= sqr(t - d);
    if (t > l + d) sum += tri(t - (l + d) - 1);
    if (t > l + u) sum += tri(t - (l + u) - 1);
    if (t > r + d) sum += tri(t - (r + d) - 1);
    if (t > r + u) sum += tri(t - (r + u) - 1);
    if (sum >= c) return true;
    return false;
}

int main()
{
    while (~scanf("%I64d%I64d%I64d%I64d", &n, &x, &y, &c))
    {
        l = x - 1, r = n - x;
        u = y - 1, d = n - y;
        ll low = 0, high = 2 * n, mid;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (solve(mid)) high = mid - 1;
            else low = mid + 1;
        }
        printf("%I64d\n", low);
    }
    return 0;
}