CDOUT5-Editorial

editorial
1

PROBLEM LINK

Practice

Contest

Author: Md Majid Jahangir

Tester : Md Majid Jahangir

Editorialist: Md Majid Jahangir

DIFFICULTY:

Easy

PREREQUISITES:

Implementation

PROBLEM:

Pratik loves playing Hopscotch with his friends and he is very good at it. It's a game where you have to jump over tiles drawn with chalk on the ground. In this version of hopscotch, The first N natural numbers are drawn on the ground. Pratik's friends will randomly place him on a tile numbered K. Pratik has to jump from the present tile to the next-to-next tile and so on to reach the end, until he can't jump anymore. He also has to keep on adding the numbers of the tile he has landed on. What will be the sum Pratik has calculated after he has completed jumping. EXPLANATION: A naïve approach will be to iterate from k till n, skipping one tile and adding the tile numbers. But this may result to a TLE. A direct expression can be formulated to calculate the sum. We can find out the number of tiles between the constraints, say X which we need to consider. Then a simple AP formula will give the sum as the series will become: k, (k+2), (k+4), …, (K+2*X) i.e. k + k * X + (1 + 2 + 3 + 4 …. + X) * 2

This will give us the answer in O(1) time for each test case.

C++ Code:

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long int lli;
int main() 
{
    lli t,n,k;
    lli ans,dist;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&k);
        dist=(n-k)/2;
        ans=k*(dist+1)+dist*(dist+1);
        printf("%lld\n",ans);
    }
        
	return 0;
}