UVA Problem 147 – Dollars Solution

UVA Problem 147 – Dollars Solution:


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

Solving Technique:

This problem is very very very very similar to uva 674 ( Coin Change ) and uva 357 ( Let me count the ways ). These problems can be used as hint or template for this problem. So if you want to solve on your own don’t look down.

In this problem a few key points are,
  1. The amount doesn’t exceed $300.00
  2. Exit / terminate program for the input of 0.00
  3. Amount can be / is a floating point number
  4. There are different values that can be used make up the decimal and the fractional portion
  5. Output should be justified with width 6 before printing input amount and width 17 afterwards then the number of ways the amount is made up of.

Solution Technique:

Instead of calculating the decimal and the fractional portion separately we can use one method to calculate the count. Since a Dollar can be made up of coins that is, $1 = 100 cents. So we can just calculate how many ways the coins can be made and that will be the answer.

For example,
  • $4.70      =      470 cents
  • $2.00      =      200 cents
  • $6.75      =      675 cents
  • $300.00  =  30000 cents

So we can put all the ways the coins can be divided to an array. Then use that calculate the count. Now whenever we can divide the amount with a specific coin we increase the count. We need calculate for all the specific coins.

Here I have given two codes, they are essentially the same. Only difference is in the second code instead of using an array to calculate the count, I have split the loop to show the calculations.

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. Compile with C++ to be safe from compile errors although some codes do work with C compiler.


Input:

0.20
2.00
4.90
6.70
8.45
0.00

 


Output:

  0.20                4
  2.00              293
  4.90             5698
  6.70            19187
  8.45            49007

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 147 - Dollars
 */

#include<stdio.h>

#define N 30002

static long long c[N];
static const unsigned coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

int main(){
    unsigned i, j;
    float n;

    c[0] = 1;
    for(i = 0; i < 11; ++i){
        for(j = coins[i]; j < N; ++j)
            c[j] += c[j - coins[i]];
    }

	while(scanf("%f", &n) == 1 && n){
        // Rounding error fix
        unsigned coin = (unsigned)((n + 0.001) * 100);

        // 6 width justified including the input amount and 17 width afterwards including count
        printf("%6.2f%17lld\n", n, c[coin]);
    }
	return 0;
}

Code (Loop Split):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 147 - Dollars ( Loop Split )
 */

#include<stdio.h>

#define N 30002

static long long c[N];

int main(){
    unsigned i, j;
    float n;

    c[0] = 1;

    /*
     * Loop Split
     */

    for(j = 5; j < N; ++j)
        c[j] += c[j - 5];

    for(j = 10; j < N; ++j)
        c[j] += c[j - 10];

    for(j = 20; j < N; ++j)
        c[j] += c[j - 20];

    for(j = 50; j < N; ++j)
        c[j] += c[j - 50];

    for(j = 100; j < N; ++j)
        c[j] += c[j - 100];

    for(j = 200; j < N; ++j)
        c[j] += c[j - 200];

    for(j = 500; j < N; ++j)
        c[j] += c[j - 500];

    for(j = 1000; j < N; ++j)
        c[j] += c[j - 1000];

    for(j = 2000; j < N; ++j)
        c[j] += c[j - 2000];

    for(j = 5000; j < N; ++j)
        c[j] += c[j - 5000];

    for(j = 10000; j < N; ++j)
        c[j] += c[j - 10000];

	while(scanf("%f", &n) == 1 && n){
        // Rounding error fix
        unsigned coin = (unsigned)((n + 0.001) * 100);

        // 6 width justified including the input amount and 17 width afterwards including count
        printf("%6.2f%17lld\n", n, c[coin]);
    }
	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 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;
}

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 10235 ( Simply Emirp ) Solution

UVA Problem 10235 ( Simply Emirp ) Solution:


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

Solving Technique:

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

I have solved this problem in two ways first one is optimized primality test and second one is Sieve of Eratosthenes.

Problem is simple with a is simple we need to check if it’s prime or not. If it is then is it emrip or just prime.

There is one critical example that wasn’t given, its given below. If a prime is reversed and the reversed number is also prime then it is emrip. Ex, 17 is prime and reverse of 17 is 71 is also prime, then 17 is emrip.

If the number is emrip we should print emrip instead prime.

Critical example: 383 is prime but not emrip. If the number is prime and reversed number is equal to original number then it is not emrip.

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


Code Explanation:

I’ve written a custom check prime function to check for primes since it’ll be called twice. If the number is prime then I reversed the number and checked if that number is also prime. Lastly I checked if the reversed number is prime and also reversed number not equal to original.


Critical Input:

999
481184
373
998001
998857
753257
823455
999999
850058
78887
999983

Output:

999 is not prime.
481184 is not prime.
373 is prime.
998001 is not prime.
998857 is emirp.
753257 is prime.
823455 is not prime.
999999 is not prime.
850058 is not prime.
78887 is prime.
999983 is emirp.

Code:

/*
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10235 ( Simply Emrip optimized primality )
 */

#include<stdio.h>
#include<math.h>

unsigned int checkPrime(unsigned int n){
    if (n == 2)
        return 1;

    if (n % 2 == 0 || n < 2)
        return 0;

    register unsigned int i;
    unsigned int len = sqrt(n);

    for (i = 3; i <= len; i += 2){
        if (n % i == 0)
            return 0;
    }

    return 1;
}

int main(){
    register unsigned int n;
    unsigned int p, prime, mod;

    while (scanf("%u", &n) == 1){

        /**
         * check if number is prime
         */
        p = checkPrime(n);  

        if (p){
            /**
             * Reverse prime
             */
            prime = n;
            mod = 1;

            while (prime / mod){
                mod *= 10;
            }
            mod /= 10;

            unsigned int reversePrime = 0;
            while (prime){
                /**
                 * Here reversePrime is the reversed prime
                 */
                reversePrime += mod * (prime % 10);
                prime /= 10;
                mod /= 10;
            }
            /**
             * Reverse prime end
             */

            if (checkPrime(reversePrime) && reversePrime != n){  /* check if reverse is prime but also check the reversed number does not match the original */
                printf("%u is emirp.\n", n);
            }else{
                printf("%u is prime.\n", n);
            }
        }else{
            printf("%u is not prime.\n", n);
        }
    }
    return 0;
}

 

Simply Emrip with Sieve of Eratosthenes:

/*
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10235 ( Simply Emrip Sieve of Eratosthenes)
 */

#include<stdio.h>
#include<math.h>

#define N 1000000

/**
 * Since value can be up to 1000000
 */
unsigned int *primes = new unsigned int[N]; 

unsigned int *SieveOfEratosthenes(unsigned int n){
    register unsigned int i = 2;

    for (; i <= n; ++i)
        primes[i] = 1;

    primes[0] = primes[1] = 0;
    unsigned int len = sqrt(n);

    for (i = 2; i <= len; ++i){
        if (primes[i]){
            for (unsigned int k = i * i; k <= n; k += i)
                primes[k] = 0;
        }
    }
    return primes;
}

int main(){
    register unsigned int n;
    unsigned int prime, mod;

    /**
     * Pre calculate sieve for every value
     */
    primes = SieveOfEratosthenes(N);    

    while (scanf("%u", &n) == 1){
        if (primes[n]){                  /* Since sieve is calculated and stored on table just do a look up */

            prime = n;
            mod = 1;

            while (prime / mod){
                mod *= 10;
            }
            mod /= 10;

            unsigned int reversePrime = 0;
            while (prime){
                reversePrime += mod * (prime % 10);
                prime /= 10;
                mod /= 10;
            }

            /**
             * Again access table to see if it is a prime
             */
            if (primes[reversePrime] && reversePrime != n)
                printf("%u is emirp.\n", n);
            else
                printf("%u is prime.\n", n);
        }else
            printf("%u is not prime.\n", n);
    }
    return 0;
}

UVA Problem 272 (TEX QUOTES) Solution

UVA Problem 272 (TEX QUOTES) Solution:


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

Solving Technique:

This problem is relatively easy. In this problem we are asked to replace a pair of quotes. The first quote replaced with two ( ` ) character and next quote replaced with two ( ‘ ) character. Besides testing with given inputs we should also test with other inputs such as inputs given below before submission.

We can also solve this problem by printing characters one by one when they are found. But that process is really slow. We should consider first creating a string for the things we want to print then print them altogether using only one printf.

Also consider making loop counter variables register. This doesn’t guarantee that variables will be stored on register but if they are then our program runs a lot faster.

Another thing is we need some kind of ON OFF switch, or Flip Flop to check when we get Grave Caret ( ` ) or when we get a single quote ( ). Here in my code the variable ( c ) is doing that job.

ASCII values instead of characters,

' 39     /* Single Quote */
` 96     /* Grave Caret */
" 34     /* Double Quote */

Important: The quotes should be considered for the whole input not line by line.


Critical Input:

""
"""
""""

Critical Output:

``''
``''``
''``''``

Code:

#include<stdio.h>

static char t[256];

int main(){
    register unsigned i, k, c = 0;

    while(gets(t)){
        char inp[256] = {'\0'};

        for (i = k = 0; t[i]; ++i){
            /*
             * ASCII decimal value of " (Double Quotes) is 34
             */
            if (t[i] == 34 && !c){
                /*
                 * ASCII decimal value of ` (Grave Caret) is 96
                 */
                inp[k] = inp[k+1] = 96;
                /*
                 * We added TWO characters
                 */
                k += 2;
                /*
                 * Flag or ON OFF
                 */
                c = 1;
            }else if(c && t[i] == 34){
                /*
                 * ASCII decimal value of ' (Single Quote) is 39
                 */
                inp[k] = inp[k+1] = 39;
                k += 2;
                c = 0;
            }else{
                /*
                 * If neither single or Double Quote found
                 */
                inp[k] = t[i];
                ++k;
            }
        }
        printf("%s\n", inp);
    }
    return 0;
}