UVa : 11516 (WiFi)


1. A house, which get the lowest coverage from any wifi access point.
we need to find the distance of that house from its nearest wifi access point.

2. if n >= m then
we can place the access point at every house
so the ans is 0.0

3. otherwise we should place the access points in between first house and last house.

4. if a house is at 1
another house is at 5
then we can place a wifi at 3
this wifi can serve both houses with maximum distance of 2

5. possible output is between 0 and 1000000
because, house number is between 0 to 1000000
and we have to place the wifi points between first and last house

6. u find an excellent explanation here, how to apply binary search and other algorithm to solve this kind of problems :
topCoder Tutorial : Turnpike

7. to get the decimal ans, i’ve run another binary search
for example, from the first binary search u find
lo = 4
hi = 5
multiplied it by 10
lo = 40
hi = 50
now run another binary between 40 and 50
output: hi / 10 . hi % 10


// http://uva.onlinejudge.org/external/115/11516.html
// Runtime : 0.060s
// Tag : binary search 

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int n, m;
int houseNo [100000 + 10];

bool check (int mid)
{
    int used = 1;
    int wifirange = houseNo [0] + mid;

    for ( int i = 0; i < m; i++ ) {
        if ( houseNo [i] > wifirange ) { wifirange = houseNo [i] + mid; used++; }
    }

    return used <= n;
}

int main ()
{
	int testCase;
	scanf ("%d", &testCase);

	while ( testCase-- ) {
        scanf ("%d %d", &n, &m);

        for ( int i = 0; i < m; i++ ) scanf ("%d", &houseNo [i]);

        if ( n >= m ) { printf ("0.0\n"); continue; }

        sort (houseNo, houseNo + m);

        int lo = 0;
        int hi = N;

        while ( hi - lo > 1 ) {
            int mid = (lo + hi) / 2;
            if ( check (mid * 2) ) hi = mid;
            else lo = mid;
        }

        lo *= 10;
        hi *= 10;

        for ( int i = 0; i < m; i++ ) houseNo [i] *= 10;

        while ( hi - lo > 1 ) {
            int mid = (lo + hi) / 2;
            if ( check (mid * 2) ) hi = mid;
            else lo = mid;
        }

        printf ("%d.%d\n", hi / 10, hi % 10);

	}

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

One thought on “UVa : 11516 (WiFi)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s