This problem is pretty straightforward except for one very bad trick. The problem requires outputting a blank line for every set processed. I got caught here and got a wrong answer in my first try.

The algorithm first calculates the total number of bricks and divides the sum by the number of stacks. the resulting number is the number of bricks for each stack so that all stacks have the same height. i call this height the fair height which is the height whereby all stacks should be equal to.

the algorithm then goes through each stack. if the height of a stack is greater than the fair height, then get the difference. sum all the differences for all stacks taller than the fair height. this sum of differences would then be equal to the minimum number of brick moves.

#include "stdio.h"

#include "string.h"

#include "stdlib.h"

int main() {

char line[1000];

char *pch;

int n, i, fair, x, moves, k;

int h[1000];

for (k = 1; 1; k += 1) {

gets(line);

sscanf(line, "%d", &n);

if(!n)

break;

gets(line);

pch = strtok(line, " \t\n");

i = 0;

while (pch) {

h[i] = atoi(pch);

pch = strtok(NULL, " \t\n");

i += 1;

}

fair = 0;

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

fair += h[i];

}

fair /= n;

moves = 0;

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

x = h[i];

if (x > fair) {

moves += (x - fair);

}

}

printf("Set #%d\n", k);

printf("The minimum number of moves is %d.\n\n", moves);

}

return 0;

}

## No comments:

## Post a Comment