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 10041 – Vito’s Family Solution

UVA Problem 10041 – Vito’s Family Solution:


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

Solving Technique:

This is a sorting problem. It requires us minimize the distance from Vito’s to every other house. That distance must be median because median value minimizes the distance from every side. So the median is the position of Vito’s house.

The problem requires us to find, “minimal sum of distances from the optimal Vito’s house to each one of his relatives”. So this means we calculate distance from Vito’s house ( Median ) to every other house and sum them. Meaning subtract position of every house from Vito’s house and sum their distance.

I have provided Three commented codes below. First one uses STL Sort and doesn’t calculate absolute value for distance. Second one shows the use of Insertion Sort and calculates absolute value to find their distance. The last one uses vector to store data and STL algorithm to find nth element in an array. Here ( for this code ) the calculated nth element is the median.

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:

2
2 2 4
3 2 4 6

 


Output:

2
4

Code ( Without Calculating Absolute Value ):

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

#include<cstdio>
#include<algorithm>

static int A[512];

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

	while (n--){
        scanf("%d", &m);

        if (m == 1){
            /**
             * If only 1 input then no need to process
             * For 1 input the distance is always Zero
             */
            scanf("%*d");
            printf("0\n");
        }

        else{
            int dist = 0, median, key;

            for (i = 0; i < m; ++i)
                scanf("%d", &A[i]);

            /**
             * Sort the input using stl sort
             * Instead of using sorting algorithm, Try to implement Selection Algorithm to find Median in O(n) time
             */
            std::sort(A, A + m);

            /**
             * Find median dividing by two or shifting bit to left once
             * here, key is the value of median
             */
            median = m >> 1;
            key = A[median];

            /**
             * here, dist is the summation of distance of every house
             * Any value less than Median can subtracted from median will result in a positive value
             */
            for (i = 0; i< median; ++i)
                dist += key - A[i];

            /**
             * No need calculate for the median so start from (median + 1)
             * In case of value greater than Median, the Median must be subtracted from that value for positive number
             * Also by removing duplicates of median we may speed up the code
             */
            for (i = median + 1; i < m; ++i)
                dist += A[i] - key;

            printf("%d\n", dist);
        }
	}
	return 0;
}

 

Code ( Insertion Sort ):

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

#include<stdio.h>
#include<stdlib.h>

static int A[512];

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

	while (n--){
        scanf("%d", &m);
        int dist = 0, median, key;

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

        /**
         * Insertion Sort:
         * Two portions sorted and unsorted
         */
        for (i = 1; i < m; ++i){
            key = A[i];
            j = i - 1;

            /**
             * Compare every element with sorted portion ( elements to its left )
             */
            while (j >= 0 && A[j] > key){

                /**
                 * While comparing shift items to right until the comparison is false
                 */
                A[j + 1] = A[j];
                --j;
            }

            /**
             * When comparison is False or done, we found the sorted position for that element so we insert it in that position
             */
            A[j + 1] = key;
        }

        /**
         * Find Median value, left shift once is divided by Two
         */
        key = A[m >> 1];

        /**
         * Since elements after Median is bigger than Median So, we need to find absolute value of them
         */
        for (i = 0; i < m; ++i){
            dist += abs(key - A[i]);
        }

        printf("%d\n", dist);
	}
	return 0;
}

 

Code ( using vector & n-th element to find median ):

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

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>

using namespace std;

int main(){
    register int n, m, i, j;
    int key, num;
    vector<int> v;

    scanf("%d", &n);
    while (n--){
        scanf("%d", &m);

        if (m == 1){
            /**
             * If only 1 input then no need to process
             * For 1 input the distance is always Zero
             */
            scanf("%*d");
            printf("0\n");
        }

        else{
            /**
             * Input an a value and push it to vector
             */
            v.clear();
            for (i = 0; i < m; ++i){
                scanf("%d", &num);
                v.push_back(num);
            }

            /**
             * sort for median
             */
            nth_element(v.begin(), v.begin() + v.size()/2, v.end());

            /**
             * Get the value of median
             */
            key = v[v.size()/2];

            /**
             * Get distance of every value from median
             */
            int dist = 0;
            for (j = 0; j < i; ++j)
                dist += abs(key - v[j]);

            printf("%d\n", dist);

        }
    }
    return 0;
}

UVA Problem 10347 – Medians Solution

UVA Problem 10347 – Medians Solution:


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

Solving Technique:

This is a simple geometrical problem. We can use Heron’s formula to calculate the area.

Use double for safety. Print 3 places after decimal point. If the area is invalid then print -1.000 ( with 3 Zeros ) after decimal point. This may be a reason for WA.

I have provided two codes. One of them uses fread and string stream ( include sstream ) to take and process input. I have commented this code for easier understanding. The other code is with out fread, stringstream and not commented.

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 Inputs:

 1  2  3
 5  9  4
 3  2  3
 4  5  3
-3 -3 -3

 


Output:

-1.000
-1.000
 3.771
 8.000
 5.196

Code:

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

#include<iostream>
#include<cstdio>
#include<sstream>
#include<cmath>

static char buffer[32768];

int main(){
    double a,b,c,s;

    /**
     * @brief Read file from stdin and create string stream of buffer
     */
	fread(buffer, 1, sizeof buffer, stdin);
	std::stringstream ss(buffer);

	while (ss >> a >> b >> c){

        /**
         * Heron's Formula: s, is semi perimeter
         */
        s = (a + b + c) / 2.0;

        /**
         * Heron's Formula: area, of a triangle
         */
        double area = (4.0 / 3.0) * sqrt(s * (s - a) * (s - b) * (s - c));

        /**
         * If area is not valid then print -1, otherwise print area
         */
        area > 0 ? printf("%0.3lf\n", area) : printf("-1.000\n");
	}
	return 0;
}

Code ( Without fread() and stringstream() ):

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

#include<iostream>
#include<cstdio>
#include<sstream>
#include<cmath>

using namespace std;

int main(){
    double a,b,c,s;

	while (scanf("%lf%lf%lf", &a, &b, &c) == 3){

        double s = (a + b + c) / 2.0;
        double area = (4.0 / 3.0) * sqrt(s * (s - a) * (s - b) * (s - c));

        if(area > 0)
            printf("%0.3lf\n", area);
        else
            printf("-1.000\n");

	}
	return 0;
}