rahimuj570's blog

By rahimuj570, history, 6 months ago, In English

NEED_HELP

problem link: https://www.spoj.com/problems/PIE/

code screenshot: https://vjudge.net/solution/snapshot/41982578

Today I try to solve the PIE-pie problem. But at first I don’t understand how to approach the solution. So I get some idea from other’s solution. Now I understand all the solution and the approach except the base condition of the binary search. Why the base condition was 1e-6 instead of 1?

Please help me…

my code:

#include<bits/stdc++.h>
using namespace std;
        #define ll long long int
        #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        #define pb push_back
ll n,f,input;
std::vector<ll> v;


bool possible(double size){
        ll totalCake=0;
        for(ll i=0; i<n; i++){
                totalCake+=((v[i]*v[i])*M_PI)/size;
        }
        return totalCake>=f;
}

int main(){
fast;
        #ifndef ONLINE_JUDGE
        freopen("inputf.in","r",stdin);
        freopen("outputf.out","w",stdout);
        #endif
        ////////////////////////////////

int t;
cin>>t;
while(t--){
        v.empty();
        cin>>n>>f;
        f++;
        int temp=n;
        while(temp--){
                cin>>input;
                v.pb(input);
        }
        sort(v.rbegin(), v.rend());
        double maxV=(v[0]*v[0])*M_PI;
        double low=0, high=maxV, mid;

//======>> HERE'S THE CONFUSION ↓
//=====↓↓↓
        while(high-low>=1e-6){
                mid=(high+low)/2;
                if(possible(mid))low=mid;
                else high=mid;
        }
        if(possible(high))cout<<high<<endl;
        else cout<<low<<endl;
}

return 0;}

Full text and comments »

  • Vote: I like it
  • -14
  • Vote: I do not like it

By rahimuj570, history, 6 months ago, In English

I don't understand how upper_bound work or give output

here's my code:

#include<bits/stdc++.h>
using namespace std;
int main(){

std::vector<int> v({2,4,1,3});
std::vector<int> v2({2,3,1,4});
auto it=upper_bound(v.begin(), v.end(),2);
auto it2=upper_bound(v2.begin(), v2.end(),2);
cout<<*it<<endl;
cout<<*it2;

return 0;}

I think upper_bound() give me next greater element of the vectors. So as according the value of *it and *it2 will be 4 and 3. But when I run the code, the output is *it=3 and *it2=4.

Output Screenshot link: https://prnt.sc/NqBCnAXtQR8P

I don't understand, what's going wrong. Can anybody clear this thing, please.

Full text and comments »

  • Vote: I like it
  • -13
  • Vote: I do not like it