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;

}

10035 - Primary Arithmetic

I get a wrong answer here. and then when i reviewed my code, i realized the error.

what i did was to extract each digit one by one from each number. to extract the first digit, get the remainder by dividing the number by 10. the remainder is the first digit. to extract the second digit, divide the quotient from the first division by 10. the remainder is the second digit. to obtain the third digit, divide quotient from the second division by 10. the remainder is the third digit, etc., etc. until you reach the 9th digit.

sum the first digit from the first number with the first digit from the second number. if the sum is greater than 9, then there is a carry of 1 in the next operation. sum the second digit from the first number and the second digit from the second number and the carry from the first operation. if the sum of the second digits with the carry is greater than 9, then there is a carry in the next operation. sum the third digit from the first number and the third digit from the second number and the carry from the previous operation. if the sum is greater than 9, then there is a carry in the next operation. Repeat the cycle until you reach the 9th digits. During the process, count the number of carries.

The error i had was I forgot to reset the carry when the sum was less than or equal to 9. This led to a wrong answer which was made me upset and depressed. After a few minutes, i reviewed my code and realized the resetting error. Overconfidence kills.

#include "stdio.h"

int main() {
  unsigned int x, y, i, rx, ry, num_carry, sum;
  bool carry;

  while (1) {
    scanf("%d %d", &x, &y);

    if (x == 0 && y == 0) {
      break;
    }

    carry = 0;
    num_carry = 0;

    for (i = 0; i < 9; i += 1) {
      rx = x % 10;
      x = x / 10;

      ry = y % 10;
      y = y / 10;

      sum = rx + ry + carry;

      if (sum > 9) {
        carry = 1;
        num_carry += 1;
      }
      else {
        carry = 0;
      }
    }

    if (num_carry > 1) {
      printf("%d carry operations.\n", num_carry);
    }
    else if (num_carry == 1) {
      printf("1 carry operation.\n");
    }
    else {
      printf("No carry operation.\n");
    }
  }

  return 0;
}

11172 - Relational Operator

This is probably the easiest problem I ever solved in UVA.

I thought that there must be some kind of trick here. Some technicality that would make the problem extra tricky and deceiving. But it looks like there's no trick or deception here. It looks like just a really easy problem.

I also discovered that gets() can be used for these types of problems, instead of my usual fgets() style.

Here's the code:

#include "stdio.h"

int main() {
  char line[100];
  int n, i, a, b;

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

  for (i = 0; i < n; i += 1) {
    gets(line);
    sscanf(line, "%d %d", &a, &b);
//   printf("A=%d, B=%d\n", a, b);

    if (a < b) {
      printf("<\n");
    }
    else if (a > b) {
      printf(">\n");
    }
    else {
      printf("=\n");
    }
  }
}

10038 - Jolly Jumpers

This is another crazy problem.

It's supposed to be straight forward, but I kept getting run time errors.

My algorithm was to create a list of checks. Whenever a difference was calculated, the checks array element with index equal to the difference was set to 1. Then once all the differences were calculated, and all the checks were marked, I verified if all check elements with indices from 1 up to n-1 were marked with 1. If all were marked with 1, then the sequence is jolly.

I thought the run time error was because I was marking a checks element that is out of bounds. So I tried increasing my checks array from 3000 to 4000. But still the run time error existed. Then I realized that if the private key was n = 3000, then the input line would be more than 3000 characters long. This meant that my usual way of getting the line from the input would not longer work.

Usually, I use this code to get input from the user:
fgets(line, 100, stdin)

But since the input line can be more than 3000 characters long, I changed the code to:
fgets(line, 1000000, stdin)

When I did this, the run time error disappeared.

Here's the code:

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

int main() {
  char line[1000000];
  int n, i, x, j, diff, is_jolly;
  int arr[4000];
  int checks[4000];
  char *pch;

  while (fgets(line, 1000000, stdin)) {
    pch = strtok(line, " \t\n");
    n = atoi(pch);

    if (n == 1) {
      printf("Jolly\n");
      continue;
    }

    for (i = 0; i < n; i += 1) {
      pch = strtok(NULL, " \t\n");
      x = atoi(pch);
      arr[i] = x;
    }

//    printf("arr: ");
//    for (i = 0; i < n; i += 1) {
//      printf("%d ", arr[i]);
//    }
//    printf("\n");

    j = n - 1;
    for (i = 1; i <= j; i += 1) {
      checks[i] = 0;
    }

//    printf("checks: ");
//    for (i = 1; i <= j; i += 1) {
//      printf("%d ", checks[i]);
//    }
//    printf("\n");

    for (i = 1; i <= j; i += 1) {
      diff = arr[i] - arr[i - 1];
      
      if (diff < 0) {
        diff = -1 * diff;
      }

//      printf("diff = %d\n", diff);

      if (diff <= 3000) {
        checks[diff] = 1;
      }
    }

//    printf("diff: ");
//    for (i = 1; i <= j; i += 1) {
//      printf("%d ", checks[i]);
//    }
//    printf("\n");

    is_jolly = 1;
    for (i = 1; i <= j; i += 1) {
      if (checks[i] != 1) {
        is_jolly = 0;
        break;
      }
    }

    if (is_jolly) {
      printf("Jolly\n");
    }
    else {
      printf("Not jolly\n");
    }
  }
}

UVA 494 Kindergarten Counting Game

I couldn't succeed in this problem. Here's my code that could not get accepted. It's quite frustrating. Wish I knew what the private key was. I think I have to let go though, as this will drive me insane if I force myself to get my code accepted. Letting go in life is quite essential to healthy and peaceful living.

What I did here was to go through a line character by character. If the current character is a letter, then turn on the switch to 1. If it is not a letter turn off the switch to 0. When the switch switches from 0 to 1, then I increment the word count. After a line is processed, the code prints the word count. Doesn't work though. huhu.

#include "stdio.h"
#include "string.h"

int main() {
char line[100];
  int word_count, i;
  bool word_found;

while (fgets(line, 100, stdin)) {
    for (i = 0, word_found = 0, word_count = 0; line[i]; i += 1)
      if ((line[i] >= 65 && line[i] <= 90) || (line[i] >= 97 && line[i] <= 122)) {
        if (word_found == 0) {
          word_count += 1;
          word_found = 1;
        }
      }
      else {
        word_found = 0;
      }

      printf("%d\n", word_count);
}

return 0;
}

Parsing words through strtok

Here's how to parse words through strtok().

#include "stdio.h"
#include "string.h"

int main() {
  char line[100];
  char *pch;

  while (fgets(line, 100, stdin)) {
    pch = strtok(line, " \t\n");
    while (pch) {
      printf("B%sE\n", pch);
      pch = strtok(NULL, " \t\n");
    }
  }

  return 0;
}

272: TEX quotes

What I did here was to use a switch.

Process the line character by character. if the current character is an unoriented double quote, check the switch. if the switch is 0, convert to ``, then switch the switch to 1. If the switch is 1, convert to '', then switch the switch to 0.

Here's a code:

#include

int main() {
  char line[100];
  int i;
  bool x = 0;

  while (fgets(line, 100, stdin)) {
    for (i = 0; line[i]; i += 1) {
      if (line[i] != '\n') {
        if (line[i] == '"') {
          if (x == 0) {
            printf("``");
            x = 1;
          }
          else {
            printf("''");
            x = 0;
          }
        }
        else {
          printf("%c", line[i]);
        }
      }
    }
    printf("\n");
  }

  return 0;
}

458: Decoder

It's been a while since I tried out UVA. am currently applying for a programming job, and the recruiter said that I need to demonstrate skills in C/C++. And so I thought I may need to try out a few programming problems before the recruiter's technical exam.

uHunt recommends that I solve 458 (Decoder). The clue for this problem is the ASCII table:

http://www.asciitable.com/

For the input:
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5

Notice that the first character is '1'. The ascii character '1' has a decimal equivalent of 49 based on asciitable.com

The output for the input above is

 *CDC is the trademark of the Control Data Corporation.

Therefore the input to output conversion is from '1' to '*'. The ascii character '1' has a decimal equivalent of 49. The ascii character '*' has a decimal equivalent of 42. 49-42 = 7. Therefore 7 is the decimal equivalence between input ascii character and output ascii character.

Just be careful with the the endline character at the end of each input line. What I did was to check each character in the input line. If the character is not equal to the endline, then convert it.

Here's the code:

#include

int main() {
  char line[100];
  char c;
  int i;

  while(fgets(line, 100, stdin)) {
    for (i = 0; c = line[i]; i += 1) {
      if (c != '\n') {
        c -= 7;
        printf("%c", c);
      }
    }
    printf("\n");
  }

  return 0;
}