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

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

10018 - Reverse and Add

This problem is pretty straight forward except for one thing. The unsigned int restriction. The problem says that the palindrome cannot be greater than 2^32 = 4,294,967,295, but somehow, just using unsigned int does not work. Unsigned int is 32-bit, and when I use this, I get wrong answer. When I tried using unsigned long long int which is equivalent to 64-bit, the code got accepted.

To read or write an unsigned long long int, I used %llu instead of the usual %d in printf() or scanf().

To get the digits of an integer, I get the remainder when the number is divided by 10. Get the remainder when the quotient is divided by 10 again. Repeat and repeat until the quotient equals 0. The series of remainders obtained correspond to the digits of the integer.

Here's an implementation that got accepted:

#include "stdio.h"

int main() {
  char line[100];
  unsigned long long int num, q, r, l, mid, ispal, rnum, pow, sum;
  int i, j, k, num_input, count;
  unsigned int array[100];

  scanf("%d", &num_input);

  for (k = 0; k < num_input; k += 1) {
    scanf("%llu", &num);

    q = num;
    l = 0;
    while (q > 0) {
      r = q % 10;
      q /= 10;
      array[l] = r;
      l += 1;
    }

    sum = num;
    count = 0;
    do {
      count += 1;
      rnum = 0;
      pow = 1;
      for (i = l - 1; i >= 0; i -= 1) {
        rnum = rnum + (array[i] * pow);
        pow = pow * 10;
      }

      sum = sum + rnum;
//      printf("sum=%d\n", sum);

      q = sum;
      l = 0;
      while (q > 0) {
        r = q % 10;
        q /= 10;
        array[l] = r;
        l += 1;
      }

      mid = l / 2;
      ispal = 1;
      for (i = 0, j = l - 1; i < mid; i += 1, j -= 1) {
        if (array[i] != array[j]) {
          ispal = 0;
          break;
        }
      }
    } while (ispal == 0);

    printf("%d %llu\n", count, sum);
  }

  return 0;
}

299 - Train Swapping

I think this problem is an implementation of the insertion sort algorithm (http://en.wikipedia.org/wiki/Insertion_sort). Given a sequence 4 3 2 1, you can perform swaps on the numbers as follows:

4 3 2 1
3 4 2 1
3 2 4 1
2 3 4 1
2 3 1 4
2 1 3 4
1 2 3 4

This gives a total of 6 swaps. Here's another sequence and the sequence of swaps performed to sort the numbers:

4 3 5 1 2

3 4 5 1 2

3 4 1 5 2

3 1 4 5 2

1 3 4 5 2

1 3 4 2 5

1 3 2 4 5

1 2 3 4 5

This gives a total of 7 swaps.

So, one can simply implement the sequence of swaps and count the swaps.

Here's the code. By the way, I used scanf("%d\n", &n) in this code. I noticed that if I don't put \n in the scanf() function, the code does not accept input properly. The scanf() has to be used with the \n character.

#include "stdio.h"

#include "string.h"

#include "stdlib.h"

int main() {

  char line[1000];

  int n, i, l, j, k, p, swaps, temp;

  int c[100];

  char *pch;

  scanf("%d\n", &n);

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

    scanf("%d\n", &l);

    gets(line);

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

    for (j = 0; j < l; j += 1) {

      c[j] = atoi(pch);

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

    }

    for (k = 1, swaps = 0; k < l; k += 1) {

      for (p = k - 1; p >= 0; p--) {

        if (c[p] < c[p+1]) {

          break;

        }

        temp = c[p];

        c[p] = c[p+1];

        c[p+1] = temp;

        swaps += 1;

      }

    }

//    printf("B");

//    for (j = 0; j < l; j += 1) {

//      printf("%d ", c[j]);

//    }

//    printf("E\n");

    printf("Optimal train swapping takes %d swaps.\n", swaps);

  }

  return 0;

}