# HackerEarth N girls problem solution

In this HackerEarth N girls problem solution, you are given n boxes and the size of the ith box is ai. You can select at most k boxes and change their size to a positive integer.

Select some boxes and paint them a Red color. These boxes must satisfy the following condition:
1. There must be no 1 <= i, j <= n such that both i, j boxes are red and ai/aj > P/Q.
Determine the maximum number of boxes that you can color in Red.

## HackerEarth N girls problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll long long#define pb push_backconst int maxn = 2e5 + 20;int a[maxn];int main(){    ios_base::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    int n , k , P , Q;    cin >> n >> k >> P >> Q;    for(int i = 0; i < n; i++)        cin >> a[i];    sort(a , a + n);    int pt = 0 , res = 0;    for(int i = 0; i < n; i++)    {        while(1LL * a[i] * Q > 1LL * P * a[pt])            pt++;        res = max(res , min(n , i - pt + 1 + k));    }    cout << res << endl;}`

### Second solution

`#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <exception>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iosfwd>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <locale>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <set>#include <sstream>#include <stack>#include <stdexcept>#include <streambuf>#include <string>#include <typeinfo>#include <utility>#include <valarray>#include <vector>#if __cplusplus >= 201103L#include <array>#include <atomic>#include <chrono>#include <condition_variable>#include <forward_list>#include <future>#include <initializer_list>#include <mutex>#include <random>#include <ratio>#include <regex>#include <scoped_allocator>#include <system_error>#include <thread>#include <tuple>#include <typeindex>#include <type_traits>#include <unordered_map>#include <unordered_set>#endifusing namespace std;const int maxn = 200100, maxv = 100, mod = 1e9 + 7, maxa = 1005, maxs = 820, maxb = 23, base = 737, base2 = 3079, mod3 = 1e7 + 19, delt = 10513;const long long inf = 2e14;const int infint = 1e9 + 11;long long max(long long x, long long y){return (x > y ? x : y);}long long min(long long x, long long y){return (x < y ? x : y);}long double a[maxn];int32_t main() {     ios_base::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    int n, k;    long double p, q;    cin >> n >> k >> p >> q;    for(int i = 0; i < n; i++)    {        cin >> a[i];    }    sort(a, a + n);    long long ans = 0;    for(int i = n - 1; i >= 0; i--)    {        long double x = (a[i] * q) / p;        int ind = lower_bound(a, a + n, x) - a;        ind = min(ind, i);        int tmp = max(0, ind - k);        ans = max(ans, i + 1 - tmp);    }    cout << ans << endl;}`