HackerRank Geometry – Sherlock and Counting

Challenge: Sherlock and Counting

Scor cont: 20.0 / 20

Submission status: Accepted

Submission score: 1.0

Submission ID: 464722521

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/sherlock-and-counting/problem

Cerinta

Watson gives Sherlock two integers, $n$ and $k$, and asks him to count the number of positive integer $i$'s such that:   
$$i \cdot (n-i) \le n \cdot k, \text{ and } i < n$$  

Given $q$ queries where each query consists of some $n$ and $k$, print the number of possible $i$'s for each query on a new line.

Input Format

The first line contains an integer, $q$, denoting the number of times Watson queries Sherlock. 		
Each of the $q$ subsequent lines contains two space-separated integers denoting the respective values of $n$ and $k$ for a query.

Output Format

For each query, print the number of $i$'s satisfying the given formula on a new line.

Constraints

- $1 \le q \le 10^5$   
- $1 \le n, k \le 10^9$

Cod sursa

#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;
}