In this

**HackerEarth Road Demolishing problem solution**King Tle4Ever just appointed Moron as the new Engineer for his country Time Limit Exceeded. In the country of Time Limit Exceeded there are n cities and there is a direct road between each pair of cities. Now cleaning up these roads costs Tle4Ever a lot of money so he wants to demolish some of the roads but not all for sure. He wants to demolish these roads in such a way that if he picks any subset of size q of these cities, than in this subset there should exist at least one pair of cities that doesn't have a direct road between them.He asks Moron to come up with a demolishing plan satisfying his conditions. Now, as Moron is not good at coming up with plans, he asks you to help him. Now as coming up with such a plan is really difficult, given n and q you have to tell minimum number of roads that you have to demolish to satisfy King's condition.

## HackerEarth Road Demolishing problem solution.

`#include<bits/stdc++.h>`

using namespace std;

#define ll long long int

int main()

{

ios_base::sync_with_stdio(false);

int t;

cin>>t;

assert(t>=1 && t<=100000);

while(t--)

{

ll n,q;

cin>>n>>q;

assert(n>=3 && n<=1000000);

assert(q>=3 && q<=n);

q--;

ll ans=n*n-(n%q)*((n+q-1)/q)*((n+q-1)/q);

ans=ans-(q-n%q)*(n/q)*(n/q);

ans/=2;

ans=(n*(n-1))/2-ans;

assert(ans>0);

cout<<ans<<endl;

}

return 0;

}

### Second solution

`#include<bits/stdc++.h>`

using namespace std;

#define ll long long int

int main()

{

ios_base::sync_with_stdio(false);

int t;

cin>>t;

assert(t>=1 && t<=100000);

while(t--)

{

ll n,q;

cin>>n>>q;

assert(n>=3 && n<=1000000);

assert(q>=3 && q<=n);

q--;

ll ans=n*n-(n%q)*((n+q-1)/q)*((n+q-1)/q);

ans=ans-(q-n%q)*(n/q)*(n/q);

ans/=2;

ans=(n*(n-1))/2-ans;

assert(ans>0);

cout<<ans<<endl;

}

return 0;

}#define ff first

#define ss second

#define TR(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )

#define ll long long

#define llu unsigned long long

#define MOD 1000000007

#define INF 2000000000

#define dbg(x) { cout<< #x << ": " << (x) << endl; }

#define all(x) x.begin(),x.end()

int main()

{

int t;

scanf("%d",&t);

assert(1 <= t && t <= 100000);

while(t--)

{

ll n,q;

scanf("%lld%lld",&n,&q);

assert(3 <= n && n <= 1000000);

assert(3 <= q && q <= n);

q--;

ll ans = n*n - (n%q)*((n+q-1)/q)*((n+q-1)/q) - (q - n%q)*(n/q)*(n/q);

ans /= 2;

ans = (n*(n-1))/2 - ans;

printf("%lld\n",ans);

}

return 0;

}

## 0 Comments