please help in explanation of the editorial
problem: 1288A Deadline
Read it thoroughly as to why we have to iterate till square root of d.
That is the important part
Found it in comments section of the editorial
useful tip would be skim through that as well,
a lot of people have similar doubts so you can even ask at times XD
and read up more
1 Like
Simple make a quadratic equation by the given inequality and since solutions are to be non negative, so make Discriminant <= 0 .
1 Like
There’s a way simpler solution…
Just iterate over x in range [1 to n]
import math
t = int(input())
while(t>0):
n,d = map(int,input().split())
flag = 0
for x in range(0,n+1):
if x + math.ceil(d/(x+1)) <= n:
flag=1
break
if flag == 1:
print("YES")
else:
print("NO")
t-=1
1 Like
i saw a lot of solutions like this being hacked
AM >= GM (a+b>=2*sqrt(ab))
x + (d/x) >= 2*sqrt(d)
hence x=sqrt(d) for minimum value of the function.
Can be done in O(1)
int main() {
int t;cin>>t;
while(t--){
int n,d;cin>>n>>d;
double mn = sqrt(d)*2.0;
if(mn<=n+1){
cout<<"YES\n";
}else cout<<"NO\n";
}
}
2 Likes
Well guess what😉 it passed system tests
2 Likes