Thursday, September 22, 2011

Leveling sectors in a circle

Problem : How to make the surface of the circular plot level in minimum number of moves

Detail:

The circular plot is divided into sectors. Each of these sectors has a level which is indicated by an integer. The sector can be either above the earth surface, in which case the integer is positive, or below the earth surface, when it will be negative. She can choose two consecutive sectors and increase the level of both the sectors by 1 at a time, which will be counted as one move. The level of sector 1 is increased when either she chooses 1 and 2 or n and 1. If she chooses 1 and 2, it is counted as a move on sector-pair 1; 2 and 3 as sector-pair 2, and so on. She can not decrease the level of the sectors. Please help her find a strategy to make the surface of the circular plot level in minimum number of moves
Input
The first line of the input gives an integer indicating the number of test cases, N. Each test case comprises of a non-zero positive even integer, n on the first line. This is followed by n integers each giving the level of the corresponding sector. A negative number signifies that the level is below the earth surface.
Output
For each test case: The output consists of n integers on a single line giving the number of moves for each sector-pair. If no such strategy is possible, print -1 at every position.
Sample Input
2
4
1 2 4 1
6
1 2 2 1 0 0

Sample Output
-1 -1 -1 -1
0 0 0 1 1 1

Solution

/*
Algo :
1. Find the maximum element in the array
2. Find the minimum element in the array

while minimum < maximum, choose the pair (min, prev(min)) or (min, next(min)) depending on the value of prev(min) and next(min)

update minimum


*/


#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int numMoves(int a[], int ret[], int n){


int mx = 0, mn = 0;

for (int i = 1; i < n; ++i ) {

if(a[mx] < a[i])
mx = i;

if(a[mn] > a[i])
mn = i;

}

int m = a[mx], prev, next;

while(a[mn] < m) {

prev = mn == 0 ? n - 1 : mn - 1;

next = mn == n - 1 ? 0 : mn + 1;


if(a[prev] <= a[next]) {

ret[prev]++;

a[prev]++;
a[mn]++;

if(a[prev] > m) return 0;

}else {

ret[next]++;

a[next]++;
a[mn]++;

if(a[next] > m) return 0;
}

copy(a, a + n, ostream_iterator<int>(cout, " "));
cout<<endl;
mn = min_element(a, a + n) - a;

}


return a[mn] == a[mx];

}


int main() {

int a[6] = {2, 1, 1, 0, 0, 2};

int ret[6] = {0};

int success = numMoves(a, ret, 6);


cout<<"\nOutput: \n";

if(success) {

copy(ret, ret + 6, ostream_iterator<int>(cout, " "));
} else{
fill_n(ostream_iterator<int>(cout, " "), 6, -1);

}
cout<<endl;
return 0;
}

0 comments:

Post a Comment