Sunday, December 28, 2014

591: box of bricks

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;
}
 



Wednesday, December 10, 2014

136: ugly numbers

This is a brute force approach. If the current number is divisible by 2, 3 or 5, then divide it by the number it is divisible by. Keep dividing until you reach 1 as long as it is divisible by 2, 3 or 5. If the current dividend is not yet 1, and it is not divisible by 2, 3 or 5, then it means that your current number is not an ugly number. This approach took 26 seconds on an i5 machine. uVA problem specs requires at most 3 seconds. Other blogs discuss using dynamic programming.

#include "stdio.h"

int main() {
    int i, x, r, is_ugly, count;

    count = 0;
    for(i = 1; 1; i += 1) {
        x = i;
        is_ugly = 1;
        while (x > 1) {
            r = x % 2;
            if (r) {
                r = x % 3;
                if (r) {
                    r = x % 5;
                    if (r) {
                        is_ugly = 0;
                        break;
                    }
                    else {
                        x /= 5;
                    }
                }
                else {
                    x /= 3;
                }
            }
            else {
                x /= 2;
            }
        }
        if (is_ugly) {
            count += 1;
            //printf("%d ", i);
            if (count >= 1500) {
                break;
            }
        }
    }
    printf("The 1500'th ugly number is %d.\n", i);

    return 0;
}

10082: WERTYU

For this problem, I created a character array, containing the keyboard characters in their original sequence. To translate a letter, i searched for the letter in the array and printed the letter that is one index before the index where the letter is located in. I had to detect spaces in the input as well. If the current letter is a space, print a space in the output as well.

#include "stdio.h"

int main() {
    char line[1000];
    int i, j;
    char orig[] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";

    while(gets(line)) {
        for(i = 0; line[i]; i += 1) {
            if(line[i] == ' ') {
                printf(" ");
                continue;
            }
            for(j = 0; orig[j]; j += 1) {
                if(line[i] == orig[j]) {
                    printf("%c", orig[j-1]);
                    break;
                }
            }
        }
        printf("\n");
    }

    return 0;
}