CodeForces - 255D Mr. Bender and Square 二分 + 边界判断

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 ≤ 109; 1 ≤ x, y ≤ n; c ≤ n2).

Output

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

Examples

Input

1
2
6 4 3 1

Output

1
2
0

Input

1
2
9 3 8 10

Output

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

题解：找一个最小符合条件的，我们可以二分枚举答案来做，然后我们怎么求时间为 t 时细胞的总数呢  假设边界是无穷大的

总数为： t * 4 + t * (t - 1) / 2  * 4   +  1  先是4个方向 然后加上 任意两方向对应的直角依次叠加 

然后就是减去超出边界的 假设到 某一边的距离为 x  超出就为 2 * (t - 1 - x) * (t - 1 - x + 1) / 2  +  t -  x 这个方向两边都超出了

再然后就是超出的部分有相交的部分 就是角上  假设点到达该角对应两边的距离为 x y 那超出部分为 (t-1-x-y)(t-1-x-y+1)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,x,y,m;
ll cul(ll p)
{
if(p<=0) return 0;
return (p+1)*p/2;
}
int judge(ll p)
{
ll a=x-1,b=y-1,c=n-x,d=n-y;
ll ans=min(p,a)+min(p,b)+min(p,c)+min(p,d)+1;
p--;
ans+=cul(p)*4-2*cul(p-a)-2*cul(p-b)-2*cul(p-c)-2*cul(p-d);
ans+=cul(p-a-b)+cul(p-b-c)+cul(p-c-d)+cul(p-d-a);
return ans>=m;
}
int main()
{
scanf("%lld%lld%lld%lld",&n,&x,&y,&m);
ll l=0,r=1e9,ans=0;
//	cout<<judge(2)<<endl;
while(l<=r)
{
ll mid=(r+l)>>1;
if(judge(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%lldn",ans);
return 0;
} 

最后

以上就是精明裙子最近收集整理的关于CodeForces - 255D Mr. Bender and Square 二分 + 边界判断的全部内容，更多相关CodeForces内容请搜索靠谱客的其他文章。