Temples Game

QUESTION

There are N temples in a straight line and K monks who want to spread their enlightening power to the entire road of temples. All the monks have an enlightenment value, which denotes the range of enlightenment which they can spread in both the directions. Since, they do not want to waste their efficiency on trivial things of the world, they want to keep their range minimum.\n\nAlso, when we say that the N temples are in a straight line, we mean that that all the temples lie on something like an X-axis in a graph.\n\nFind the minimum enlightenment value such that all the temples can receive it.\n\nInput Format:\nThe first line contains two integers, N and K – denoting the number of temples and number of monks. The next line contains N integers denoting the position of the temples in the straight line.\n\nOutput format:\nPrint the answer in a new line.

“TESTCASE_1”: “3 2\n1 5 20\n###—###SEPERATOR—###—\n2”, “TESTCASE_2”: “10 8\n1001 3357 1125 8369 7226 9388 852 6291 9573 8165\n###—###SEPERATOR—###—\n93”, “TESTCASE_3”: “5 3\n6 12 22 45 67\n###—###SEPERATOR—###—\n8”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <bits/stdc++.h>
using namespace std;
 
#define sd(a) scanf("%d", &a)
#define ss(a) scanf("%s", &a)
#define sl(a) scanf("%lld", &a)
#define clr(a) memset(a, 0, sizeof(a))
#define debug(a) printf("check%d\n", a)
#define F first
#define S second
#define PB push_back
#define ll long long
 
int check(int num, int temples[], int N, int monks)
{
	int prev = temples[0] + num;
	monks--;
 
	for ( int i = 1 ; i < N ; i++ )
	{
		if ( prev + num >= temples[i] )
			continue;
		if ( monks == 0 )
			return 0;
		prev = temples[i] + num;
		monks--;
	}
	return 1;
}
 
int main()
{
	// ios_base::sync_with_stdio(false);
	// freopen("input.in", "r", stdin);
	int N, K;
	sd(N); sd(K);
	int* temples = new int[N];
	for ( int i = 0 ; i < N ; i++ )
	{
		sd(temples[i]);
	}
	sort(temples, temples + N);
	int lo = 0, hi = 10000000, mid;
	while ( lo < hi )
	{
		mid = (lo+hi) / 2;
 
		if ( check(mid, temples, N, K) )
		{
			if ( !check(mid-1, temples, N, K) )
			{
				break;
			}
			else
			{
				hi = mid-1;
			}
		}
		else
		{
			lo = mid + 1;
		}
	}
	mid = (lo+hi)/2;
	printf("%d", mid);
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.