My issue
for 3rd test case
20 6 18
the possible number of cases is coming out to be 165, and when i tried it manually, i still find 165 to be the correct ans
the pairs would be
(4,1)
(5,1) (5,2)
(6,1) (6,2) (6,3)
similarly it would go till
…(17, 14)
if we count these pairs it would be
1+2+3+4+…+14 which would be equal to 105
then for a=18, 19 and 20
we would add 20 for each case so additional 60 pairs would be added making the total number of pairs to be 165
My code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
ll n, k, h;
cin>>n>>k>>h;
ll count=0, ans;
ll a=2;
while (a<=n){
ans=0;
if (a>=h){
count=count+n;
a++;
continue;
}
ll l=1, r=a;
while (l<=r){
ll mid=(l+r)/2;
if ((a*k-mid*k)>=h){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
count=count+ans;
a++;
}
cout<<count<<endl;
}
int main(){
ll t;
cin>>t;
while (t--){
solve();
}
}
Problem Link: Amphibian Escape Practice Coding Problem