Problem Name :  The Playboy Chimp

Problem Link : See Problem : Uva – 10611

Its a so much easier Binary Search related Problem…
You have to think 4 Scenario for solving this problem  it will be,
1 . N(height of Luchu)<=1st Lady.
2. N>=Last Lady.
3. You will find N between heights of the all chimps.
4. Or, Exact N is  missing in heights of the all chimps !!!

Solution  :

#include<bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)

typedef long long LL;

using namespace std;


int main()
{
    LL l, n, x, q, N, temp = -99999999999999999;
    vector<LL>a;
    cin>>n;
    rep(i,n){cin>>x; if(x!=temp){a.pb(x); temp = x;}}
    n = a.size();
    cin>>q;
    rep(i,q)
    {
        cin>>N;
        LL low = 0, mid = n/2, up = n - 1, f = 1;
        if(N<=a[low]){if(a[low]==N){cout<<"X "<<a[low+1]<<endl;} else{cout<<"X "<<a[low]<<endl;}}
        else if(N>=a[up]){if(a[up]==N){cout<<a[up-1]<<" X"<<endl;} else{cout<<a[up]<<" X"<<endl;}}
        else
        {
            while(f)
            {
                if(a[mid]==N){cout<<a[mid-1]<<" "<<a[mid+1]<<endl; f = 0; break ;}
                else if(N<a[mid]&&N>a[mid-1]){cout<<a[mid-1]<<" "<<a[mid]<<endl; f = 0; break ;}
                else if(N>a[mid]&&N<a[mid+1]){cout<<a[mid]<<" "<<a[mid+1]<<endl; f = 0; break ;}
                else if(N>a[mid]){ low = mid ; mid = (low + up)/2;}
                else if(N<a[mid]){ up = mid; mid = (low+up)/2;}
            }
        }
    }
    return 0;
}
Advertisements