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

103 阅读 0 评论 68 点赞

我是靠谱客的博主精明裙子，最近开发中收集的这篇文章主要介绍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

6 4 3 1

Output

Input

9 3 8 10

Output

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

#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;
}