আলোচনাঃ
আমাকে একটা value d দেয়া হবে, আমাকে এমন দুইটা সংখ্যা a,b বের করতে
হবে যাদের যোগফল ও গুণফল পরস্পর সমান হয়।
উত্তরঃ
এটাকে mathematically লিখলে দাঁড়ায় a+b=d—(1) and a*b=d—(2) তাহলে দুইটা equation পাচ্ছি। এখন equation solve করলেই উত্তর পেয়ে যাব।
From (2), we get, a=d/b—–(3)
put this value into (1),
d/b+b=d
=>(d+b^2)/b=d
=> (d+b^2)=db
=> d+b^2-db=0
=> b^2-db+d=0 —–(4)
(4) কে a(x)^2 + bx + c = 0 এর সাথে তুলনে করে পাই,
a=1 , b= – d, c=d and x=b
we know, x=(-b±√(b^2-4ac))/2a
So, b=(-(-d) + √((-d)^2-4*1*d))/2.0*1 [big number]
and b=(-(-d) – √((-d)^2-4*1*d))/2.0*1 [small number]
Here, (d^2-4*1*d) >=0 [otherwise ‘d’ will be complex number]
=>(d^2) >= 4*1*d
So, d >= 4
বাইনারি সার্চঃ
আমাকে এখানে দুইটা নম্বর বের করা লাগবে যেন তাদের যোগফল ও গুণফল পরস্পর সমান হয়।
তাই আমরা প্রথমে একটা নম্বর guess করতে পারি। যদি guess করা নম্বর টা a=mid
হয় তাহলে b=(d-mid) হবে। এখন এদের যোগফল always d এর সমান হবে কিন্তু
গুণফল a+b এর থেকে কম/বেশি হবে। তো আমাদের দরকার a আর b এর গুণফল যাতে
সমান হয়। তাই a,b এর যেকোনো টাকে সামনে নিব আর অন্যটাকে পিছনে পাঠাবো।
এভাবে করতে করতে এক সময় a আর b এর গুণফল সমান হবে।
|(a+b)−a⋅b|≤10−6 এর মানে কি?
ধরা যাক, (a+b) এর মান আসছে 15.2378930309
আর (a*b) এর মান আসছে 15.2378930317 এখন, |(a+b)−a*b|= 8*10^-10 হয় যা 10^-6 থেকে কম। অর্থাত (a+b) আর (a*b) যখন প্রায় সমান হবে তখন তাদের difference ও অনেক কম হবে। difference (10^−6) মানে হচ্ছে (a+b) আর (a*b) এর মান দশমিক এর পরের অন্তত 6 digit পর্যন্ত মিলতে হবে । তাহলেই difference <= 10^-6 এর থেকে কম বা সমান হবে।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
int main(){
double t,mid,low,high,d,first,second;
cin>>t;
for(int i=0;i<t;i++){
cin>>d;
if(d==0){
cout<<"Y 0.000000000 0.000000000\n";
continue;
}
else if(d>0 && d<4){
cout<<"N\n";
}
else{
double big=(d+sqrt(d*d-4*d))/2.0;
double small=(d-sqrt(d*d-4*d))/2.0;
printf("Y %.9lf %.9lf\n",big,small);
}
}
}
---------------------------------- OR --------------------------------------
#include<bits/stdc++.h>
using namespace std;
int main(){
double t,mid,low,high,d,big,small;
cin>>t;
for(int i=0;i<t;i++){
cin>>d;
if(d>0 && d<4){
cout<<"N\n";
continue;
}
if(d==4){
cout<<"Y 2.000000000 2.000000000\n";
continue;
}
low=0.0,high=d;
int cnt=100;
while(cnt--){
mid=low+(high-low)/2.0;
big=mid;
small=(d-big);
if(big*small>big+small){
low=mid;
}
else{
high=mid;
}
}
printf("Y %.9f %.9f\n",big,small);
}
}
---------------------------------- OR --------------------------------------
#include<bits/stdc++.h>
using namespace std;
int main(){
double t,mid,low,high,d,big,small;
cin>>t;
for(int i=0;i<t;i++){
cin>>d;
if(d>0 && d<4){
cout<<"N\n";
continue;
}
if(d==4){
cout<<"Y 2.000000000 2.000000000\n";
continue;
}
low=0.0,high=d;
int cnt=100;
while(cnt--){
mid=low+(high-low)/2.0;
big=mid;
small=(d-big);
if(big*small>big+small){
high=mid;
}
else{
low=mid;
}
}
printf("Y %.9f %.9f\n",small,big);
}
}