UVA Problem 1586 – Molar mass Solution

UVA Problem 1586 – Molar mass Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

Formula to solve this problem is given in the description. Also i have explained in the comments. The only corner case may be two atom numbers. 

Our formula is to multiply element with its atom count to get the total weight. Since there are two digits. The first one is in 10’s position so it must be multiplied by 10. Then add the next digit to it. Since we took the input as string. So this method converts the string digits to integer.

Now just multiply that value with the weight of the corresponding molecule to get the result.

Here i have provided to two codes. The first code follows the formula given in the problem. The second one is slightly modified and strength reduced pre-calculated version based on the first code.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

4 
C 
C6H5OH 
NH2CH2COOH 
C12H22O11

Output:

12.010 
94.108 
75.070 
342.296

Code ( Commented):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

#define C 12.01
#define N 14.01
#define O 16.00
#define H 1.008

static char s[128];

int main(){
    register int n, i;
    scanf("%d", &n);

    while(n--){
        scanf("%s", &s);
        float sum = 0;

        for(i = 0; s[i]; ++i){
            /**
             * Check if it is a compound identifier
             */
            unsigned compoundCheck = s[i] == 'C' || s[i] == 'N' || s[i] == 'O' || s[i] == 'H';

            /**
             * Has only two digit next to it
             * Check if it is a compound identifier and next two digits are atom count
             */
            if(compoundCheck && (s[i + 1] >= '0' && s[i + 1] <= '9') && (s[i + 2] >= '0' && s[i + 2] <= '9')){

                /**
                 * calculate the weight with first digit in 10's position so multiply with 10
                 * Add that to the next atom count ( digit )
                 * Minus 48 convert char to its integer equivalent
                 */
                unsigned dualDigitAtom = (s[i + 1] - 48) * 10 + s[i + 2] - 48;

                switch(s[i]){
                case 'C':
                    sum += C * dualDigitAtom;
                    break;
                case 'N':
                    sum += N * dualDigitAtom;
                    break;
                case 'O':
                    sum += O * dualDigitAtom;
                    break;
                case 'H':
                    sum += H * dualDigitAtom;
                    break;
                }
            }

            /**
             * Has only one digit next to it
             * Check if it is a compound identifier and next digit is atom count
             */
            else if(compoundCheck && (s[i + 1] >= '0' && s[i + 1] <= '9')){

                unsigned singleDigitAtom = s[i + 1] - 48;

                switch(s[i]){
                case 'C':
                    sum += C * singleDigitAtom;
                    break;
                case 'N':
                    sum += N * singleDigitAtom;
                    break;
                case 'O':
                    sum += O * singleDigitAtom;
                    break;
                case 'H':
                    sum += H * singleDigitAtom;
                    break;
                }
            }

            /**
             * Single atom compound meaning no digit next to it
             */
            else if(compoundCheck && (s[i+1]!='C' || s[i+1]!='N' || s[i+1]!='O' ||s[i+1]!='H')){
                switch(s[i]){
                case 'C':
                    sum += C;
                    break;
                case 'N':
                    sum += N;
                    break;
                case 'O':
                    sum += O;
                    break;
                case 'H':
                    sum += H;
                    break;
                }
            }
        }
        printf("%.3f\n", sum);
    }
    return 0;
}

Code ( Precomputed Strength Reduction Faster ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

static char s[128];

#define H 1.008
#define C 12.01
#define O 16.0
#define N 14.01

int main(){
    register unsigned int n, i;
    unsigned int i1, i2;
    scanf("%u", &n);

    while(n--){
        scanf("%s", &s);
        float sum = 0;

        for(i = 0; s[i]; ++i){
            i1 = s[i + 1];
            i2 = s[i + 2];
            unsigned i1check = i1 >= '0' && i1 <= '9';

            switch(s[i]){
            case 67:
                if(i1check && (i2 >= '0' && i2 <= '9')){
                    sum += 120.1 * i1 + C * i2 - 6341.28;
                    break;
                }else if(i1check){
                    sum += C * i1 - 576.48;
                    break;
                }else{
                    sum += C;
                    break;
                }
            case 72:
                if(i1check && (i2 >= '0' && i2 <= '9')){
                    sum += 10.08 * i1 + H * i2 - 532.224;
                    break;
                }else if(i1check){
                    sum += H * i1 - 48.384;
                    break;
                }else{
                    sum += H;
                    break;
                }
            case 78:
                if(i1check && (i2 >= '0' && i2 <= '9')){
                    sum += 140.1 * i1 + N * i2 - 7397.28;
                    break;
                }else if(i1check){
                    sum += N * i1 - 196.14;
                    break;
                }else{
                    sum += N;
                    break;
                }
            case 79:
                if(i1check && (i2 >= '0' && i2 <= '9')){
                    sum += 160.0 * i1 + O * i2 - 8448.0;
                    break;
                }else if(i1check){
                    sum += O * i1 - 768.0;
                    break;
                }else{
                    sum += O;
                    break;
                }
            }
        }
        printf("%.3f\n", sum);
    }
    return 0;
}
Advertisements

UVA Problem 299 – Train Swapping Solution

UVA Problem 299 – Train Swapping Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

The problem specifically asks to “find the least number of swaps of two adjacent carriages necessary to order the train”. That’s it.

It is a sorting problem and we have to count the number of swap between adjacent carriages. So a stable must be applied. Here I have provided three codes with insertion sort, bubble sort, merge sort.

Even though merge sort is O(n lg n) because input size is so small ( 0 <= L <= 50 ) it doesn’t make much difference. For Bubble sort though no need to perform swaps 🙂 just count it. A hybrid between insertion and merge sort me be a slight performance booster. I will try to include it later.

The problem UVA 11462 age sort is solved also with merge sort among other sort algorithms. A commented version merge sort can be found there.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

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

Output:

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

Code ( Bubble Sort No Swap ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Bubble Sort No Swap)
 */

#include<stdio.h>

/**
 * c is swap count
 */
static int A[64], c;

int main(){
    int n, i, j, m;
    scanf("%d", &n);

    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * Bubble Sort
         */
        for(i = 0; i < m - 1; ++i){
            for(j = i + 1; j < m; ++j){
                /**
                 * No need to swap elements
                 * This code may be moved input loop
                 */
                if(A[i] > A[j])
                    ++c;
            }
        }

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

Code ( Insertion Sort ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Insertion Sort)
 */

#include<stdio.h>

static int A[64], c;

int main(){
    register int n, i, j;
    int m, key;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * Insertion sort using inner for loop
         */
        for(i = 1; i < m; ++i){
            key = A[i];
            for(j = i - 1; j >= 0 && A[j] > key; --j){
                A[j + 1] = A[j];
                ++c;
            }
            A[j + 1] = key;
        }

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

Code ( Merge Sort Swap Count ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Merge Sort)
 */

#include<stdio.h>
#include<limits.h>

static int A[64], c;

void Merge(int front, int mid, int rear){
    int n1 = mid-front+1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void Mergesort(int front, int rear){
    if(front < rear){
       int mid = (rear + front) >> 1;
       Mergesort(front, mid);
       Mergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    int n, i, j, m;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * To understand Merge sort see my UVA solution age sort 11462
         */
        Mergesort(0, m - 1);

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