# HackerEarth Road to playoffs problem solution

In this HackerEarth Road to playoffs problem solution In a football championship, N teams are competing against each other on the league stage. The current number of points of each team are X1, X2, X3....XN. M days of league stage are remaining and on each day K teams win and each of the winning team's points is incremented by 1. Top B teams will qualify for the playoffs in the championship. Officials of the tournament want to how many teams have a non-zero probability of making it to the playoffs.

Note: If points of certain teams are equal, any of the teams can qualify for playoffs and each team has equal probability.

## HackerEarth Road to playoffs problem solution.

`#include<bits/stdc++.h>using namespace std;#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define mod 1000000007#define endl "\n"#define test ll t; cin>>t; while(t--)typedef long long int ll;bool check(vector<ll>&a,ll mid,ll n,ll m,ll k,ll p){    ll total=0;    for(ll i=0;i<n;i++){        if(i+1<p || i>=mid){            total+=m;        }        else{            if(a[i]>a[mid]+m){                return false;            }            total+=(a[mid]+m-a[i]);        }    }    return (total>=m*k);}int main() {    FIO;    test    {        ll n,m,k,b; cin>>n>>m>>k>>b;        vector<ll>a(n);        for(auto &it:a) cin>>it;        sort(a.begin(),a.end(),greater<ll>());        ll ans=b,st=b,dr=n-1;        while(st<=dr){            ll mid=(st+dr)/2;            if(check(a,mid,n,m,k,b)){                ans=mid+1;                st=mid+1;            }            else{                dr=mid-1;            }        }        cout<<ans<<endl;    }    return 0;}`

### Second solution

`from math import inft = int(input())while t > 0:    t -= 1    n, m, k, b = map(int, input().split())    a = list(map(int, input().split()))    a.sort(reverse=True)    lo = b - 1    hi = n    while hi - lo > 1:        i = (lo + hi) // 2        need = m * (k - (b - 1) - (n - i))        for j in range(b - 1, i):            if a[j] > a[i] + m:                need = inf            else:                need -= a[i] + m - a[j]        if need > 0:            hi = i        else:            lo = i    print(lo + 1)`