We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Geometry
  4. Sherlock and Counting
  5. Discussions

Sherlock and Counting

  • k4droid3
     + 0 comments

    Btw, it's also possible to pass test cases in this perticular problem using Binary Search. just find the max possible i between 1 and n/2, where, i.(n-i) <= n.k and the answer is two times that. also need to take care of the edge case of n/2 . (n - n/2) <= n . k.

    #include <iostream>

#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; ~i; i--)
#define pb push_back
#define ff first
#define ss second

using namespace std;
typedef long long ll;
const ll MOD=1000000007;

void solve(){
    ll n, k;
    cin >> n >> k;

    if(n/2 * (n-n/2) <= n*k || n==1) {
        cout << n-1 << '\n';
        return;
    }

    ll l=1, r=n/2;
    while(l <= r){
        ll mid = l + (r-l)/2;

        if(mid*(n-mid) <= n*k) l=mid+1;
        else r=mid-1;
    }

    cout << 2*r << '\n';
}

int main(){
#ifdef k4droid3
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while(t--)
        solve();
    
    return 0;
}