Soluție HackerRank pentru Sherlock and Counting, subdomeniul Geometry, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Sherlock and Counting
- Domeniu: Geometry
- Limbaj: C++14
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
Cerință
Watson gives Sherlock two integers, n and k, and asks him to count the number of positive integer i's such that:
i · (n-i) ≤ n · 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 ≤ q ≤ 10^5
- 1 ≤ n, k ≤ 10^9
Cod sursă
#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;
}