UVA Problem 12149 – Feynman Solution

UVA Problem 12149 – Feynman Solution:


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

Solving Technique:

The problem asks given a number n how many squares are there in n by n grid. The relation can be found out by drawing n*n sqares and counting the squares. Since it will be very hard to draw and count more than 4 by 4 grid. We can try 1 by 1, 2 by 2, 3 by 3, 4 by 4 grid and count the number of squares. From there we can try to guess an equation.

For,
1*1 grid =   1 Square = 1
2*2 grid =   5 Square = 1 + 2^2
3*3 grid = 14 Square = 1 + 2^2 + 3^2
4*4 grid = 30 Square = 1 + 2^2 + 3^2 + 4^2

Here the series is,
1^2 + 2^2 + 3^2 + 4^2 + ….. n^2
Which is the sum of first n squares.

Instead of calculating with this formula a simpler formula exists.
1^2 + 2^2 + … + n^2 = n(n + 1)(2n + 1) / 6

The proof for this formula can be found here.

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. Please compile with c++ compiler as some of my codes are in c and some in c++.


Input:

2
1
8
0

Output:

5
1
204

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 12149 Feynman
 * Type:    Mathematics ( 1^2 + 2^2 + .... + n^2 )
 */

#include<stdio.h>

int main(){
    static unsigned n;

    while(scanf("%u",&n) && n)
        printf("%u\n", n * (n + 1) * (2 * n + 1 ) / 6 );

    return 0;
}
Advertisements

UVA Problem 11727 – Cost Cutting Solution

UVA Problem 11727 – Cost Cutting Solution:


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

Solving Technique:

Very easy problem. We are given 3 numbers in each test case. Among those three numbers we need to print the median value.

Two codes given below one solved with simple if else branching, another one is solved using STL sort algorithm. Can be solved also using stl nth_element  but it is too much for this problem. Use of nth_element shown in UVA Problem 10041 Vito’s Family.

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. Please compile with c++ compiler as some of my codes are written in c and some in c++.


Input:

3
1000 2000 3000
3000 2500 1500
1500 1200 1800

 


Output:

Case 1: 2000
Case 2: 2500
Case 3: 1500

Code C:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 11727 - Cost Cutting
 */

#include<stdio.h>

int main(){
    static unsigned i, n, a, b, c;
    scanf("%u", &n);

    for(i = 1; i <= n; ++i){
        scanf("%u%u%u",&a,&b,&c);

        if(a > b && a > c)
            printf("Case %u: %u\n", i, b > c ? b : c);
        else if(b > c)
            printf("Case %u: %u\n", i, c > a ? c : a);
        else
            printf("Case %u: %u\n", i, a > b ? a : b);
    }
    return 0;
}

Code STL Sort:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 11727 - Cost Cutting
 */

#include<cstdio>
#include<algorithm>

static unsigned a[4];

int main(){
    static unsigned i, j, n;
    scanf("%u", &n);

    for(i = 1; i <= n; ++i){
        for(j = 0; j < 3; ++j)
            scanf("%u", &a[j]);

        std::sort(a, a + 3);
        printf("Case %u: %u\n", i, a[1]);
    }

    return 0;
}

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

UVA Problem 11965 – Extra Spaces Solution

UVA Problem 11965 – Extra Spaces Solution:


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

Solving Technique:

This problem is very straightforward. We just need to skip outputting consecutive spaces. Instead of multiple spaces only print one space.

The only problem for this problem may be outputting a blank line between test cases. This can be handled in many ways. I have shown one method below. I have commented the code below, have a look.

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.


Critical Input:

4
3
Sample test one:
  there was     2 spaces and 
here are also  2  spaces
2
Sample test two:
     there was 4 spaces
3
Sample         test one:
  there was 2 spaces and 
here are also  2    spaces
2
Sample test two:
     there was 4 spaces

 


Output:

Case 1:
Sample test one:
 there was 2 spaces and 
here are also 2 spaces

Case 2:
Sample test two:
 there was 4 spaces

Case 3:
Sample test one:
 there was 2 spaces and 
here are also 2 spaces

Case 4:
Sample test two:
 there was 4 spaces

 

Code:

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

#include<cstdio>

static char buffer[1024];

int main(){
	register unsigned int n, m, c = 0;
	scanf("%u", &n);

	while (n--){

        /*
         * Use getchar() before reading a string or character to discard the newline character,
         * Otherwise newline character will be taken taken by the string or character input function
         */
        scanf("%u", &m); getchar();

        /*
         * Only print newline between test cases
         */
        if (c) printf("\n");

        ++c;
        printf("Case %u:\n", c);

        while (m--){
            gets(buffer);

            register unsigned i = 0, spaces = 1;
            unsigned val;

            for (; val = buffer[i]; ++i){

                /*
                 * Cutting Comparison
                 * @example use this code {{ val = val == ' ' }}
                 * replace {{ val == ' ' }} statements with just {{ val }}
                 */

                /*
                 * If a space found after non space character then print a space
                 */
                if (val == ' ' && spaces){
                    printf(" ");
                    spaces = 0;
                    continue;
                }

                /*
                 * If consecutive space are found skip them
                 */
                if (val == ' ') continue;

                /*
                 * Print non space characters
                 */
                printf("%c", buffer[i]);
                spaces = 1;
            }
            printf("\n");
        }
	}
	return 0;
}

UVA Problem 673 – Parentheses Balance Solution

UVA Problem 673 – Parentheses Balance Solution:


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

Solving Technique:

This problem can be solved easily using Stack ( also check out these problems i have solved using stack uva 11192uva 483 ).  Here the only corner case is space character. Input only contains three types of character 1st bracket, 3rd bracket and a space character.

Here i have provided three solutions. All have same logic. But first one is well commented and written for easier understanding. Second one is modified version of first. For the first and second code i take input as string but in the last i take input one by one as characters.

In the second code i have checked if length is odd then i know it can’t be balanced. So i just print NO. Which is “strlen(par) & 1“. It is equivalent to “strlen(par) % 2 == 1” meaning string length is odd.

The logic for this code is whenever we find a closing bracket it must have its corresponding opening bracket before ( to its immediate left ) that. So we remove those two and keep processing rest of the input. Example,

[ [(  )]  ()]

Here we do nothing ( or, store them in string ) when we find an opening bracket. Whenever we find a closing bracket we see the character before that ( to its left ) is its opening bracket. If this condition doesn’t match then there is error in the input. So break immediately. Also when we find a closing bracket with its opening bracket we remove them and process rest of the input. Example,

[ [(  )]  ()]  /* our input */
[ [] ()]       /* we remove first occurrence of closing and its corresponding opening bracket to its left */
[ ()]          /* Process rest of the input */
[ ]
               /* Here nothing is left so it is a valid input */

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.


Critical Input:

More Critical inputs can be found in this link,

https://gist.github.com/quickgrid/72b1adc38d8752cd6905

3
([])
(([()])))
([ ()[  ]  ( )])()

Output:

Yes
No
Yes

Code Usage of Stack ( Explained ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>

/**
 * Size for our stack although they said 128 but stack safety
 */
#define SIZE 256

/**
 * Our stack or array to hold parenthesis
 */
static char stack[SIZE];
/**
 * Our stack index counter
 */
int top = -1;

/**
 * Push function of out stack, We basically store the character and increase the counter
 * Checking of stack overflow is not implemented since stack size is large enough for this program
 */
void push(char c){
    stack[++top] = c;
}

/**
 * Set the element in current index to NUL and decrease the index
 * Stack underflow never occurs for this program
 */
void pop(){
    stack[top--] = '\0';
}

int main(){
    register unsigned n, i;
    unsigned char c;

    /**
     * Scan the test case count, getchar() is needed because i used gets() below which takes away my new line if getchar() is not used
     */
    scanf("%u", &n); getchar();

    while (n--){
        stack[SIZE] = {'\0'};
        /**
         * Reset the stack index, meaning we start using our stack array from the beginning
         */
        top = -1;
        /**
         * If no error then error is 0 else if there is error then error is 1
         */
        unsigned error = 0;

        /**
         * Our character array to take the input string
         */
        char *par = new char[SIZE + 1];
        gets(par);

        for (i = 0; par[i]; ++i){
            /**
             * Corner case the input can have space
             */
            if(par[i] == ' ')
                continue;

            /**
             * Push the character to stack if open bracket
             */
            if(par[i] == '[' || par[i] == '(')
                push(par[i]);

            /**
             * Pop or remove the element from top of stack if matching closing bracket found
             */
            else if(par[i] == ']' && stack[top] == '[')
                pop();
            else if(par[i] == ')' && stack[top] == '(')
                pop();

            else{
                /**
                 * If matching closing bracket not found then set error flag to 1 (ON)
                 */
                error = 1;
                /**
                 * Since we found a mistake there is no need to process rest of the string
                 */
                break;
            }
        }

        /**
         * If error flag is on or there still exist some brackets on stack then print NO
         */
        if(error || top > -1)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

Taking input as string:(Faster)

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>
#include<string.h>

static char stack[256];
static char par[256];
int top;

int main(){
    unsigned n, error;

    scanf("%u", &n);
    getchar();

    while(n--){
        gets(par);

        if(strlen(par) & 1)
            printf("No\n");
        else{
            stack[256] = {'\0'};
            top = -1;
            error = 0;

            for(unsigned i = 0; par[i]; ++i){
                if(par[i] == ' ')
                    continue;

                if(par[i] == '[' || par[i] == '(')
                    stack[++top] = par[i];
                else if((par[i] == ')' && stack[top] == '(') || (par[i] == ']' && stack[top] == '['))
                    --top;
                else{
                    error = 1;
                    break;
                }
            }

            (error || top > -1) ? printf("No\n") : printf("Yes\n");
        }
    }
    return 0;
}

Taking input one by one as characters:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>

#define SIZE 256

char stack[SIZE];

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

    while(n--){
        register int top = -1;
        unsigned error = 0;

        while ((ch = getchar()) != '\n'){
            if (ch == ' ') continue;
            if (ch == '[' || ch == '(') stack[++top] = ch;
            else if ((ch == ']' && stack[top] == '[') || (ch == ')' && stack[top] == '(')) --top;
            else error = 1;
        }

        if (error || top > -1) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

UVA Problem 12894 – Perfect Flag Solution

UVA Problem 12894 – Perfect Flag Solution:


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

Solving Technique:

Rank 38, Run time 9 ms ( 0.009 s ).

This problem may seem very hard if we don’t read it carefully. Also there is no need to use floating point numbers to solve this problem. Also no need to worry about negative length or widths. In case you forgot about Ratio.

Here are the key points,

1. length (L) to width ratio of 10:6,
>> length / width = 10 / 6
>> 6 * length = 10 * width
>> 3 * length = 5 * width

2. length (L) to radius ratio of 5:1,

>> length / radius = 5 / 1
>> 1 * length = 5 * radius

3. Example: If the length is 10, then width should be 6 and radius should be 2.
Set these values in our equations above and check if both sides are equal.

4. Its center (Circle’s) will be placed on the intersecting point of thee perpendicular drawn from the nine-twentieth part of the length of the flag,

>> nine-twentieth of length, ( 9 / 20 ) * length
>> Circles x distance on flag = given x position of circle - initial x position
>> 20 * (circle center x - initial x) = 9 * length

5. Horizontal line drawn through the middle of its width,

>> Circle middle y distance = given circle y - initial y
>> middle of width, (1/2) * width
>> 2 * ( given circle y - initial y ) = width

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
0 0 20 12 9 6 4
0 0 10 6 4 3 2
1 1 21 13 10 7 4
0 0 20 20 9 10 4

Output:

YES
NO
YES
NO

Code (with given Formula):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 12894 ( Perfect Flag )
 */

#include<stdio.h>

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

    while (n--){
        int x0, y0, x1, y1, cx, cy, r;
        scanf("%u%u%u%u%u%u%u", &x0, &y0, &x1, &y1, &cx, &cy, &r);

        unsigned len = x1 - x0;
        unsigned wid = y1 - y0;

        if (( 5 * wid == 3 * len ) && ( len == 5 * r ) && 20 * ( cx - x0 ) == 9 * len && 2 * ( cy - y0 ) == wid)
            printf("YES\n");
        else
            printf("NO\n");

    }
    return 0;
}

 Another in C++ ( Without Optimization ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 12894 ( Perfect Flag )
 */

#include<iostream>

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    register unsigned n;
    unsigned int x0, y0, x1, y1, cx, cy, r;

    std::cin >> n;
    while (n--){
        std::cin >> x0 >> y0 >> x1 >> y1 >> cx >> cy >> r;
        unsigned len = x1 - x0, wid = y1 - y0;
        (( 5*wid == 3*len ) && ( len == 5*r ) && (20*( cx - x0 ) == 9*len) && ((( cy-y0 ) << 1) == wid) ) ? std::cout << "YES\n" : std::cout << "NO\n";
    }

    return 0;
}

 Code (Strength Reduction Optimization based on the first code):

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 * Problem UVA 12894 ( Perfect Flag )
 */
#include<stdio.h>

int main(){
    unsigned n, x0, y0, cx, cy, r;
    scanf("%u", &n);

    while (n--){
        scanf("%u%u%*u%*u%u%u%u", &x0, &y0, &cx, &cy, &r);

        if (2 * ( cx - x0 ) + ( y0 - cy ) == 3 * r)
            printf("YES\n");
        else
            printf("NO\n");

    }
    return 0;
}

UVA Problem 1368 – DNA Consensus String Solution

UVA Problem 1368 – DNA Consensus String Solution:


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

Solving Technique:

Rank 174, Run time 12 ms ( 0.012 s ).

First input is number of test cases. Next of two inputs one is number of strings to input and another is the size of string. Our strings will only contain A, C, G, T characters.

For solving this problem we first need to find consensus string. That is of all strings we check each column of all strings and count the maximum occurring character in that column. This character is our consensus string character for that column.

Consensus string size is same as the input string size. Since each of its characters are maximum occurring characters in the input string. Example,

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
========
TAAGATAC    /* Consensus String, check each column for max character count */

Now that we have found the consensus string we just need to find consensus error. I will only explain the logic here, I have commented my code below.

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
========
TAAGATAC    /* Consensus String */
========
11101021    /* Consensus Error, 1+1+1+0+1+0+2+1 = 7, count every character of a column that don't match that consensus string character */

Now if you understood my explanation time to go write a better solution :).

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 
5 8 
TATGATAC 
TAAGCTAC 
AAAGATCC 
TGAGATAC 
TAAGATGT 
4 10 
ACGTACGTAC 
CCGTACGTAG 
GCGTACGTAT 
TCGTACGTAA 
6 10 
ATGTTACCAT 
AAGTTACGAT 
AACAAAGCAA 
AAGTTACCTT 
AAGTTACCAA 
TACTTACCAA

Output:

TAAGATAC 
7 
ACGTACGTAA 
6 
AAGTTACCAA 
12

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 1368 ( DNA Consensus String )
 */

#include<stdio.h>

int main(){
    register unsigned n, a, b, i, j, k, error;
    scanf("%u", &n);

    while(n--){
        scanf("%u%u", &a, &b);

        /**
         * Create the string array
         */
        char **s = new char*[a+1];
        for(i = 0; i < a; ++i){
            /**
             * Allocate space for each string
             */
            s[i] = new char[b+1];
            /**
             * Input a string in i th position
             */
            scanf("%s", s[i]);
        }

        /**
         * Consensus string declaration
         */
        char *conseq = new char[b+1];
        /**
         * K is used below
         */
        for(k = i = 0; i < b; ++i){
            /**
             * Reset A,C,G,T count array
             */
            unsigned int seq[4] = {0};
            for(j = 0; j < a; ++j){
                switch(s[j][i]){
                case 65:    /* 65, 'A' here seq[0] is A */
                    ++seq[0];
                    break;
                case 67:    /* 'C' */
                    ++seq[1];
                    break;
                case 71:    /* 'G' */
                    ++seq[2];
                    break;
                case 84:    /* 'T' */
                    ++seq[3];
                }
            }

            unsigned max = seq[0], maxIndex = 0;
            for(j = 1; j < 4; ++j){
                if(seq[j] > max){
                    /**
                     * Find the max count of A,C,G,T in a column, in all strings
                     */
                    max = seq[j];
                    /**
                     * Remember the maxIndex for creating consensus string
                     */
                    maxIndex = j;
                }
            }

            /**
             * We keep adding to our consensus string the most count of A,C,G,T
             */
            switch(maxIndex){
            case 0:
                conseq[k++] = 65;
                break;
            case 1:
                conseq[k++] = 67;
                break;
            case 2:
                conseq[k++] = 71;
                break;
            case 3:
                conseq[k++] = 84;
            }
        }

        for(error = i = 0; i < b; ++i){
            for(j = 0; j < a; ++j){
                /**
                 * Calculate the error count by moving column by column of all strings, then comparing against the consensus string character in that column
                 */
                if(s[j][i] != conseq[i])
                    ++error;
            }
        }

        /**
         * Print the consensus string and error count EACH ON A NEW LINE
         */
        printf("%s\n%u\n", conseq, error);
    }
    return 0;
}

UVA Problem 11879 – Multiple of 17 Solution

UVA Problem 11879 – Multiple of 17 Solution:


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

Solving Technique:

Run time 0.009 s ( 9 ms ), Rank 868.

This problem requires us to take input as a string. We have to use a string since no built in data type can hold 10^100 digits. Although there maybe other ways to solve this ( JAVA BIG INTEGER ) but i will focus on C++.

We could solve this problem by dividing the input and in the end checking if there is no remainder. Here i take each digit of the input then check if it is divisible by 17. If it is not divisible then i keep multiplying by 10 each time and sum current digit to it. In the end if there is no remainder ( meaning remainder is ZERO ) then the input is divisible by 17.

Another way to write that one line of code below,

remainder = remainder * 10;           /* For the first iteration remainder is set to 0 */
remainder = remainder + s[i] - '0';   /* s[i] is a character, - 48 makes it an Integer */
remainder = remainder % 17;

The above piece of code is iterated for the whole input string.

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:

34
201
2098765413
1717171717171717171717171717171717171717171717171718
0

Output:

1
0
1
0

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11879 ( Multiple of 17 )
 */

#include<stdio.h>

static char s[128];

int main(){
    register unsigned int i;
    unsigned remainder;

    while(gets(s)){
        if(s[0] == 48 && s[1] == 0) return 0;                   /* 48 is character '0' and 0 is '\0' NUL character */

        for(remainder = i = 0; s[i]; ++i)
            remainder = ( remainder * 10 + s[i] - 48 ) % 17;    /* Keep multiplying the remainder by 10 and add the current digit, then mod by 17 to get remainder */

        remainder ? printf("0\n") : printf("1\n");              /* If the number is divisible by 17 then remainder in the end becomes ZER0 */
    }
    return 0;
}

UVA Problem 1585 – Score Solution

UVA Problem 1585 – Score Solution:


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

Solving Technique:

Easy problem.  Run time 0.009 s ( 9 ms ), Rank 439.

We are given a string with only ‘O’ and ‘X’ characters. Also it is specified string length is not bigger than 80 character and there won’t be any space in between characters.

The way to calculate the score is,

OOXXOXXOOO
1200100123 /* 1+2+0+0+1+0+0+1+2+3 = 10 */

We count up until we encounter an ‘X’. Then we reset count to ZERO. Before reset we keep a sum of all previous counts. 

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:

5 
OOXXOXXOOO 
OOXXOOXXOO 
OXOXOXOXOXOXOX 
OOOOOOOOOO 
OOOOXOOOOXOOOOX

Output:

10 
9 
7 
55 
30

Code:

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

#include<stdio.h>
static char s[128];

int main(){
    register unsigned n, i;

    scanf("%u", &n);

    while (n--){
        scanf("%s", s);
        unsigned sum = 0, val = 0;

        for (i = 0; s[i]; ++i){

            /**
             * 79 is decimal ASCII 'O', Applying XOR Check to see if they are equal
             * If two numbers are same then val is set to 0, otherwise increment val
             */
            (s[i] ^ 79) ? val = 0: ++val;

            sum += val;
        }

        printf("%u\n", sum);
    }
    return 0;
}

UVA Problem 12854 – Automated Checking Machine Solution

UVA Problem 12854 – Automated Checking Machine Solution:


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

Solving Technique:

For This problem I tried many times but best I could get was rank 116 and run time 0.009 s ( 9 ms ). This is really bad for a very simple code.

The logic is simple we are given two strings ( or, 10 integers ) . If the character in the same index / position of the two strings are different we print Y. Otherwise if the characters are same we print N.

Since I know that there will 5 and 5 total of 10 characters each time. So I used integer to take input.

Now I used XOR between to integers because applying XOR to two integers if they are equal then we get 0. Otherwise we get a 1. XOR table,

a b a^b
0 0  0
0 1  1
1 0  1
1 1  0

So that is what I need if they are same i get 0 and else I get 1. Using this logic I check all 10 values. Then use ternary operation to print Y or, N.

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:

1 1 1 1 1
0 0 0 0 0
1 1 0 1 0
0 0 1 0 1
1 0 0 1 0
1 0 1 1 0

Output:

Y
Y
N

Code:

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link https://quickgrid.wordpress.com
 * Problem: UVA 12854 - Automated Checking Machine
 */

#include<stdio.h>
int main(){
    register unsigned int a,b,c,d,e,f,g,h,i,j;
	while (scanf("%u%u%u%u%u%u%u%u%u%u", &a, &b, &c, &d, &e, &f, &g, &h, &i, &j) == 10){
        (a ^ f && b ^ g && c ^ h && d ^ i && e ^ j) ? printf("Y\n"): printf("N\n");
	}
	return 0;
}