UVA Problem 264 – Count on Cantor Solution

UVA Problem 264 – Count on Cantor Solution:


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

Solving Technique:

Warning this is a terrible dynamic programming and memoization solution. If you want a fast and efficient solution then, this isn’t what you are looking for.

Problem Statement:

Given an input integer that represent a rational number sequence term shown by cantor, output the rational number for that term.


Solution Types:

I have given two solution, one of which uses a 2D array to store the rational number sequence as shown by cantor and using a traversal pattern memoize the series in another array. Although the first one can be improved to only traverse 1/4 th of the array but that’s still a lot.

The next solution discards the 2D array and using the traversal pattern with some optimization memoizes the series.

The time difference as of UVA submission running time is,

0.245 ms (1st technique)
0.072 ms (2nd technique)

Removing the recursion by replacing with iterative version ( A bit harder to do ) will make it even faster. I think this one can be further improved but have no idea how.

Figuring out the algorithm:


Note everything here is assuming indexing starts from 1 instead of 0. But in my code I start with index 0 instead of 1.

 

Sequence Traversal within Matrix:
cantor sequence matrix
cantor sequence matrix

Unraveling the Sequence:
cantor sequence chain
cantor sequence chain

Traversal Pattern and Sub structure/pattern:
cantor structure and substructure pattern
cantor structure and substructure pattern

Substructure and Movement within Matrix:
cantor movement within matrix
cantor movement within matrix

Points To Notice:

1. Moves right when row number is 0 and column number is even.
2. Moves down-left when row number is 0 and column number is odd.
3. Moves down when column number is 0 and column number is odd.
4. Moves up-right when column number is 0 and column number is even.
5. Diagonal traversal gets bigger by 1 unit for each down or right movements.


Traversing the Matrix:

Traverse(r,c,index,diagonal) =     \begin{cases}      \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\     \swarrow \text{(c - 1 times)} & \forall : row = 0; col \in Odd \\     \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\     \nearrow \text{(r - 1 times)} & \forall : col = 0; row \in Even \\    \end{cases}

OR, In my code,

Traverse(r,c,index,diagonal) =     \begin{cases}      \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\     \swarrow \text{(c + diagonal times)} & \forall : row = 0; col \in Odd \\     \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\     \nearrow \text{(r + diagonal times)} & \forall : col = 0; row \in Even \\    \end{cases}

Note: Increment the index and diagonal also.


Filling the Matrix (1st code only):

CantorTable_{i,j} =     \begin{cases}      numerator = row, & \forall : Column, rows \\     denominator = column, & \forall : Column, rows \\    \end{cases}


Base case:

Note when row or the column is equal to 0 then there is a turn. If row or column becomes less than 0 then it should stop.

Also the amount values to memoize is N which is the maximum cantor sequence value for this problem. So if N values are memoized then the process should stop.

if (r < 0 || c < 0 || index > M)
    return;

Storing the fractions in 2D Struct Array:

Instead of storing the values in string it is better to store the fraction in a struct. There are 3 things in the fraction the numerator, a division sign , the denominator. There is no need to store the division sign since all elements within matrix are fraction.

struct CantorSequence{
    int numerator;
    int denominator;
};

About Space:

The first solution requires a total of O( M + \frac{N(N+1)}{2} ) space including storing the cantor sequence in another array and pre calculating the 2D cantor table and traversing.

The second solution requires a total of O( M ) space including storing the cantor sequence in another array.

Here, M is 10000000 and N is 4500. N can be adjusted but 4500 is a safe value.


Please point out if the post contains mistakes.

 

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++.


More Inputs of This Problem on uDebug.


Input:

3
14
7
10000000 

 


Output:

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4
TERM 10000000 IS 2844/1629

Code Recursive DP 2D struct Traversal and Memoize:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 264 - Count on Cantor
 *
 * Technique: Zig Zag / Spiral Diagonal traversal,
 *            2D struct array,
 *            2D half diagonal fill,
 *            Recursive Dynamic Programming
 ***********************************************************************/


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

// N * N should be almost twice greater than or equal to M.
// Or, N should be such that N*(N+1)/2 is greater than M.
#define N 4500


#define M 10000000


/**
 * Table to construct the sequence
 */
struct CantorTable{
    int numerator;
    int denominator;
} CT[N][N];


// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];


/**
 * Fill in the cantor table.
 */
void CantorFill(){

    for(int row = 0; row < N; ++row){

        int cutoff = N - row;

        for(int col = 0; col < cutoff; ++col){
            CT[row][col].numerator   = row + 1;
            CT[row][col].denominator = col + 1;
        }

    }

}


void RecursiveCantor(int r, int c, int index, int diagonal){

    // base case
    if( r < 0 || c < 0 || index > M ){
        return;
    }


    OrderedCantor[index].numerator = CT[r][c].numerator;
    OrderedCantor[index].denominator = CT[r][c].denominator;



    // Amount of times to travel in diagonal
    ++diagonal;



    if(r == 0){

        // when odd move down left
        if(c % 2){
            for(int i = 0; i < c + diagonal; ++i){
                ++index;
                r = r + 1;
                c = c - 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

        // when even Move right
        else{
            ++index;
            c = c + 1;
            RecursiveCantor( r, c, index, diagonal );
        }
    }

    if(c == 0){

        // when odd move down
        if(r % 2){
            ++index;
            r = r + 1;
            RecursiveCantor( r, c, index, diagonal );
        }

        // when even Move up right
        else{
            for(int i = 0; i < r + diagonal; ++i){
                ++index;
                r = r - 1;
                c = c + 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

    }

}



int main() {


    // Initialize Cantor table
    CantorFill();


    // Pass in row, column, index, diagonal traversal size
    RecursiveCantor(0, 0, 1, 0);


    int n;


    while( scanf("%d", &n) == 1 ){
        printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
    }

    return 0;
}


Code Recursive DP Sequence Memoize:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 264 - Count on Cantor
 *
 * Technique: Zig Zag / Spiral Diagonal traversal,
 *            Recursive Dynamic Programming
 ***********************************************************************/


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


#define M 10000000


/**
 * Table to construct the sequence
 */
struct CantorTable{
    int numerator;
    int denominator;
};


// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];




void RecursiveCantor(int r, int c, int index, int diagonal){

    // base case
    if( r < 0 || c < 0 || index > M ){
        return;
    }


    // change from table traversed DP
    OrderedCantor[index].numerator = r + 1;
    OrderedCantor[index].denominator = c + 1;


    // Amount of times to travel in diagonal
    ++diagonal;



    if(r == 0){

        // when odd move down left
        if(c % 2){
            for(int i = 0; i < c + diagonal; ++i){
                ++index;
                r = r + 1;
                c = c - 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

        // when even Move right
        else{
            ++index;
            c = c + 1;
            RecursiveCantor( r, c, index, diagonal );
        }
    }

    else if(c == 0){

        // when odd move down
        if(r % 2){
            ++index;
            r = r + 1;
            RecursiveCantor( r, c, index, diagonal );
        }

        // when even Move up right
        else{
            for(int i = 0; i < r + diagonal; ++i){
                ++index;
                r = r - 1;
                c = c + 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

    }

}



int main() {

    // Pass in row, column, index, diagonal traversal size
    RecursiveCantor(0, 0, 1, 0);


    int n;


    while( scanf("%d", &n) == 1 ){
        printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
    }

    return 0;
}
Advertisements

UVA Problem 444 ( Encoder and Decoder ) Solution

UVA Problem 444 ( Encoder and Decoder ) Solution:


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

Solving Technique:

Seems like a medium level problem ( at least for me ).

Here the input is either mix of characters (A-Z) or (a-z) or,

!  ,  .  :  ;  ?

These characters. Or, Integers only.

If the input is a decoded string such as, abc?.  We need to encode it. The encode method is to reverse the Ascii values. For example, If decoded string was input

Input: abc?d
Just Convert to Ascii: 97989963100
Reverse the Converted Ascii: 00136998979 /*This is our output*/

If the input was an encoded integer string, to decode it follow the procedure below,

Input: 00136998979
Reverse the input: 97989963100
Convert to Character: abc?d /*This is our output*/

Another important thing any characters from ‘d’ to ‘z’ has ASCII value of 100 or more. So In that case we need to reverse 3 characters to find its corresponding ASCII character ( in other words to decode properly ).

Also after encoding a string if there are 0’s in the front we should print them like in the example above.

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:

The code below makes cin, cout as fast as or maybe even faster then scanf, printf. Reference code forces blog.

std::ios_base::sync_with_stdio(false);
cin.tie(0);

It is also advised to use new line character instead of endl.


Input:

abc
798999
Have a Nice Day !

Output:

998979
cba
332312179862310199501872379231018117927

Code:

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

#include<iostream>
#include<stdio.h>

using namespace std;

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

    int i, j, a;
    string s;

    while (getline(cin, s)){
        /*
         * Find out the length of string
         */
        for (i = 0; s[i]; ++i);

        /*
         * Start processing the string/input backward
        */
        for (j = i - 1; j >= 0;){
            /*
             * Check if the input is encoded integer. Also checking with s[0] or the first character is enough since it can either be numbers or letters
            */
            if (s[0] >= '0' && s[0] <= '9'){
                /*
                 * Check if the character is of length 2 because No input below 100 Ascii value of (d) contains integer length 2
                 */
                if (s[j] != '1'){
                    /*
                     * Make the last digits 10s and 1st digit in 1s place. Ex: 79 = 7+(9*10) = 97
                     */
                    a = (s[j-1] - '0') + (s[j] - '0') * 10;
                    /*
                     * Decrease the loop counter by two since we have processed two digits. Meaning the integer was 99 or below
                     */
                    j -= 2;
                }else{
                    /*
                     * Make the last digits 100s, middle 10s and 1st digit in 1s place. Ex: 101 = 1+(0*10)+(1*100) = 101
                     */
                    a = s[j-2] - '0' + (s[j-1] - '0') * 10 + (s[j] - '0') * 100;
                    /*
                     * Decrease the loop counter by Three since we have processed Three digits. Meaning the integer was 100 or above
                     */
                    j-=3;
                }
                /*
                 * Since the input was a number and we decoded it to a character now just print that character
                 */
                cout << (char)a;
            }
            /*
             * If not encoded integer it is obviously a string
             */
            else{
                /*
                 * Store the ASCII integer value of the character
                 */
                a = s[j];

                while (a){
                    /*
                     * Print the last integer digit of (a)
                     */
                    cout << a % 10;
                    /*
                     * Discard the last digit
                     */
                    a /= 10;
                }
                /*
                 * Decrease the loop counter since One character is processed
                 */
                --j;
            }
        }
        cout << endl;
    }
    return 0;
}

UVA Problem 11428 ( Cubes ) Solution

UVA Problem 11428 ( Cubes ) Solution:


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

Solving Technique:

In this problem we are to find the value of “x” and “y”, given “N” from the formula below,

N = x– y3

If there are no solution just print “No solution” ( without quotes ).

One line that may be confusing is, “If there is more than one solution then output the one with smallest value of y”.

Looping from 1 to square root N is enough. Also an important statement is checking if “x” cube is greater than “N”. Otherwise we calculate we will get a negative result. Because if “x” cube is less than or equal “n”, then there is another “y” cube subtracted from it so it will become negative but we were given positive numbers.

 for(x=1; x<=sqrt(n);){
     if(x*x*x > n){
      /*check for y code goes here*/
     }
     ++x;
 }

If “x” cube is greater than “N” then it may be a possible value of “x”. Now we need to calculate for “y” to make sure. In order to do that we loop “j” from 1 to x-1 ( We can’t loop till i otherwise x and y will be equal which result in 0. Also we loop from 1 because subtracting 0 doesn’t change anything ).

/*reaches here only if x cube is greater than N*/

for(y=1; y<x;){
    if(x*x*x - y*y*y == n){
        works = 1;        /* set flag for breaking outer loop and printing x y */
        break;            /* break inner loop since x cube minus y cube is equal to N, means we found the answer */
    }
    ++y;
}
if(works) break;          /* break the outer loop since we found the answer we should loop anymore */

Now i check if “x” cube minus “y” cube is equal to N. In that case i use a flag set it as true ( 1 ) and break the loop. It is important that if the flag is true we exit the outer loop otherwise it’ll keep looping and will give us wrong answer.

That’s it now just print value of x y or, No solution.

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.


Input:

7
37
12
0

Output:

2 1
4 3
No solution

Code Without Optimization:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */

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

int main(){
	int n;

	while (scanf("%d", &n) && n){
        int works = 0, x, y;

        for (x = 1; x <= sqrt(n);){
            if (x*x*x > n){
                for (y = 1; y < x;){
                    if (x*x*x - y*y*y == n){
                        works = 1;
                        break;
                    }
                    ++y;
                }
                if (works) break;
            }
            ++x;
        }

        if (works){
            printf("%d %d\n", x, y);
        }else{
            printf("No solution\n");
        }
	}
	return 0;
}

 

With Some Optimization:

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

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

int main(){
    register unsigned x, y;
    unsigned n, k;

    while (scanf("%u", &n) && n){
        unsigned works = 0;

        for (x = 1, k = sqrt(n); x <= k;){
            unsigned xcube = x * x * x;

            if (xcube > n){
                for (y = 1; y < x;){
                    if (xcube - y * y * y == n){
                        works = 1;
                        break;
                    }
                    ++y;
                }

                if (works)
                    break;
            }
            ++x;
        }

        if (works)
            printf("%u %u\n", x, y);
        else
            printf("No solution\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 575 ( Skew Binary ) Solution

UVA Problem 575 ( Skew Binary ) Solution:


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

Solving Technique:

This one is very easy. We need to un-skew or convert to decimal the given input using the given formula.

Inputs are string/ character array because the inputs won’t fit on another data type. Plus it is easier with string.

It is already said after converting our inputs to it will fit in integer data type. Also unsigned can be used here since none of the input, output or calculation result will be zero.

We just need to calculate the formula and print the result.

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:

Here taking an array of size 32 ( 31+1 for safety  ) will be enough. Code is commented for more look below.


Input:

10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0

Output:

44
2147483646
3
2147483647
4
7
1041110737

Code:

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

#include<stdio.h>

/**
 * My custom recursive function to calculate power of two
 */
unsigned int twoPow(unsigned int n){    
    if(n == 0)
        return 1;

    /**
     * this is our recursive counter we need to decrease it otherwise it will go to infinite loop
     */
    n--;    

    /**
     * simply keep multiplying 2 given times to get power of two
     */
    return 2 * twoPow(n); 
}

int main(){
    char s[32];
    unsigned int i,j,sum;   /* here i used unsigned since none of our input or outputs are negative */
    
    while (gets(s)){
        /*
         * check if its 0 then exit, Maybe even deleting the NULL check will work for this problem
         */
        if(s[0] == '0' && s[1] == '\0')    
            return 0;
        
        sum = 0;

        /**
         * get the string length
         */
        for(i = 0; s[i]; ++i);  
        
        for(j = 0; s[j]; ++j)
        /**
         * convert character to integer, then multiply 2 to the power n, then subtract 1 and add to sum
         */
            sum = sum + (s[j] - 48) * (twoPow(i - j) - 1);  
        
        printf("%u\n", sum);
    }
    return 0;
}

UVA Problem 12614 ( Earn For Future ) Solution

UVA Problem 12614 ( Earn For Future ) Solution:


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

Solving Technique:

Like many other programming problem this tries to tangle us with its complex language and useless data to through us off the right path. I have provided three working solutions with same logic but with some optimizations.

This program simply requires us to find the max number among given inputs.

At first glance it may seem like we need to bitwise & ( and ) all given value for the result. But trying that doesn’t yield the right answer.

If you need to know what this problem is about:

The problem says bitwise operation will be performed on card numbers. But we do not need to perform bitwise operations. It is not our concern. But the problem also says that he have picked N cards. Now he needs to choose more cards to maximize his gain. The problem say, ” Please tell him the maximum amount he can win from these set of cards”. This means we obviously need to pick the biggest number because we want to maximize the amount ( performing bitwise & ( and ) with the biggest number instead of a smaller gives us a bigger number ).

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:

The first line of input is the number of test cases ( n ). The next line of input the number of inputs (I used m in my code) to come. Following m lines inputs.

Here we do not need an array to store the variable. We can just calculate as the values are being given. For every test case I use the first card number as the max number, then I compare other inputs against it.


Input:

6
2
0 1
2
3 5
3
0 1 2
4
0 0 9 1
5
0 99 1 9 5
6
8 0 7 5 8 5

Output:

Case 1: 1
Case 2: 5
Case 3: 2
Case 4: 9
Case 5: 99
Case 6: 8

 Using some assumption:

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 * Problem UVA 12614 ( Earn For Future )
 */

#include<stdio.h>

int main(){
    register unsigned n, i;
    /*
     * Since we are told we won't get any negative numbers
     */
    unsigned m, a, max, c = 1;

    scanf("%u", &n);
    while (n--){
        /*
         * Assuming m is at least 1, so i scan the first one as max
         */
        scanf("%u%u", &m, &max);
        /*
         * Already one input taken, so decrease counter
         */
        m -= 1;
        while (m--){
            scanf("%u", &a);
            if (a > max)
                max = a;
        }
        printf("Case %u: %u\n", c++, max);
    }
    return 0;
}

Another one with custom scanning and some bit-wise tricks:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 12614 ( Earn For Future )
 */

#include<stdio.h>

void Rfastscan(register unsigned &x){
    register int c;
    x = 0;
    c = getchar();
    for(;(c > 47 && c < 58); c = getchar())
        x = (x << 1) + (x << 3) + c - 48;
}

void fastscan(int &x){
    unsigned neg = 0;
    register int c;
    x = 0;
    c = getchar();

    if(c == '-'){
        neg = 1;
        c = getchar();
    }

    for(;(c > 47 && c < 58); c = getchar())
        x = (x<<1) + (x<<3) +c -48;
    if(neg)
        x = ~x+1;   /* 2's complement */
}

int main(){
    register unsigned n, m, i, c = 1;
    int a, max;

    Rfastscan(n);
    while(n--){
        Rfastscan(m);
        fastscan(max);

        for(i=1; i<m; ++i){
            fastscan(a);
            if(a > max)
                max = a;
        }
        printf("Case %u: %u\n", c++, max);
    }
    return 0;
}

UVA Problem 12541 ( Birthdates ) Solution

UVA Problem 12541 ( Birthdates ) Solution:


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

Solving Technique:

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

This problem seems easy at first glance but requires some thinking. There will be only two output.

First one will be the name of the youngest person ( The person whose was born after everyone ). Meaning his/her birth year, month, date is greater than others. Ex, a person born on 1991 is younger than person born on 1990.

Second one will be the name of the oldest person ( The person whose was born before everyone ). Meaning his/her birth year, month, date is less than others. Ex, a person born on 1990 is older than person born on 1991.

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:

Since the name doesn’t exceed 15 letter so an array of size 16 ( i use 1 more for safety ) will suffice. Next there are 4 inputs each time. One is name string, the rest are integers such as date, month and year respectively.

Since the inputs are all related I used a struct to keep all data in a structure named person.

Now I use two more struct variable named young and old. By default I set both of them to first value of our structure. Now I compare if year is greater I set young to that struct variable in that loop. If less than I set old to the struct variable in that loop. If both of these are not true then I follow the same logic for month and date.

In the and the young and old struct variable get set to youngest and oldest struct variable based on logic.

Since I only need to print the youngest and oldest person name so, I just access our young and old structure with name property using dot operator and print them each on a new line.


Input:

10
Machel 31 12 4999
Amar 27 9 1991
Conrad 1 1 1999
Kara 18 9 5001
Tom 29 1 1991
Priyanka 1 12 5001
Melissa 25 10 1991
Ping 16 10 5001
Amidala 10 1 1991
Xena 17 10 5001

Output:

Priyanka
Amidala

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 12541 ( Birth dates  )
 */
 
#include<stdio.h>

struct person{
    char name[16];
    unsigned int date, month, year;
};

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

    scanf("%u", &n);

    struct person p[n], maxp, minp;

    for(; i<n; ++i){
        scanf("%s%u%u%u", &p[i].name, &p[i].date, &p[i].month, &p[i].year);
    }

    maxp = p[0];    /*younger person*/
    minp = p[0];    /*older person*/

    for(i=0; i<n; ++i){
        if(p[i].year > maxp.year)
            maxp = p[i];

        else if(p[i].year < minp.year)
            minp = p[i];

        else{
            if(p[i].month > maxp.month && p[i].year >= maxp.year)
                maxp = p[i];

            else if(p[i].month < minp.month && p[i].year <= minp.year)
                minp = p[i];

            else{
                if(p[i].date > maxp.date && p[i].month >= maxp.month && p[i].year >= maxp.year)
                    maxp = p[i];
                else if(p[i].date < minp.date && p[i].month <= minp.month && p[i].year <= minp.year)
                    minp = p[i];
            }
        }

    }

    printf("%s\n%s\n", maxp.name, minp.name);

    return 0;
}

Console based Dice Game Code C

A Console based turn based dice rolling game. The player with highest number on dice wins. If both have same dice then the game draws.

CODE:

#include<stdio.h>
#include<time.h>
#include<stdbool.h>

#define TOTAL_PLAYERS 2

int rollDices(int sides);
int tossCoin();
void exitMessage();
void invalidOp();
void playerDiceOptions(int tc, int sides);

struct player
{
    char name[100];
    bool played;
    int dice;
} p[TOTAL_PLAYERS];


int main()
{
    int sides = 6;
    char tcAgree = '\0';


    for(int i=0; i<TOTAL_PLAYERS; i++)
    {
        printf("Enter Player %d name:\n", i+1);
        scanf("%s", &p[i].name);
    }


    int tc = tossCoin();
    printf("Toss COIN: (Y/N)?\n");
    getchar();
    tcAgree = getchar();


    printf("\n");
    if(tcAgree - 'y'==0|| tcAgree - 'Y'==0)
    {
        printf("Player %d \"%s\" will play first\n", tc+1, p[tc].name);
        p[tc].played = true;
    }
    else if(tcAgree - 'n'==0 || tcAgree - 'N'==0)
    {
        exitMessage();
        return 0;
    }
    else
    {
        invalidOp();
        return 0;
    }

    playerDiceOptions(tc, sides);


    //invert the player
    if(tc==0)
        tc=1;
    else
        tc=0;

    printf("\n");
    for(int i=0; i<TOTAL_PLAYERS; i++)
    {
        if(!p[i].played)
        {
            printf("Player %d \"%s\" will play\n", i+1, p[i].name);
            playerDiceOptions(tc, sides);
        }
    }

    printf("\n");
    Sleep(2000);

    int k=0;
    if(p[k].dice>p[k+1].dice)
        printf("Player %d \"%s\" wins\n", k+1, p[k].name);
    else if(p[k].dice<p[k+1].dice)
        printf("Player %d \"%s\" wins\n", (k+1)+1, p[k+1].name);
    else
        printf("the game is a draw\n");

    return 0;
}

int rollDices(int sides)
{
    int dice1 = rand() % sides + 1;
    return dice1;
}

int tossCoin()
{
    srand(time(NULL));
    return rand() % 2;
}

void exitMessage()
{
    printf("Exiting.....");
    Sleep(2000);
}

void invalidOp()
{
    printf("Invalid Operation\n");
}

void playerDiceOptions(int tc, int sides)
{
    char rollAgree = '\0';

    printf("Roll dice: (Y/N)\n");
    getchar();
    rollAgree = getchar();
    if(rollAgree - 'y'==0|| rollAgree - 'Y'==0)
    {
        p[tc].dice = rollDices(sides);
        printf("Player %d \"%s\" got on dice: %d\n", tc+1, p[tc].name, p[tc].dice);
    }
    else if(rollAgree - 'n'==0 || rollAgree - 'N'==0)
    {
        printf("I get it you don't want to play\n");
        exitMessage();
        return 0;
    }
    else
    {
        printf("Invalid operation\n");
        return 0;
    }
}

Console based Static Clock with Structure C

Create a 24 hour clock with struct that takes hour, minutes, seconds as input. First check if inputs are valid. The output is 1 second plus the input. Input format is (H M S) hour, minute then second.

Input:

2 3 9
4 2 59
8 59 59
23 59 59

Output:

2 : 3 : 10
4 : 3 : 0
9 : 0 : 0
0 : 0 : 0

CODE:

#include<stdio.h>

struct time{
 short _h, _m, _s;
} t;

int main(){
   while(1){
       printf("Enter Hour, Minute, Second:\n");
       scanf("%d %d %d", &t._h, &t._m, &t._s);
       if(t._h<0 || t._h>23 || t._m<0 || t._m>60 || t._s<0 || t._s>60)
           printf("\nWrong input try again!\n\n");
       else break;
       printf("\n");

       if(++t._s == 60)
           t._s = 0;
       if(++t._m == 60)
           t._m = 0;
       if(++t._h == 24)
           t._h = 0;
    }
    printf("%d : %d : %d\n", t._h, t._m, t._s);
    return 0;
}