UVA Problem 10921 – Find the Telephone Solution

UVA Problem 10921 – Find the Telephone Solution:


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

Solving Technique:

Given a string of alphabets (A-Z), 1, 0, and Hyphens( – ) task for this problem is to find numbers represented by a character from the given table.

1, 0, Hyphen should not be changed since they aren’t in table. Just change a character with its integer representation from table. Easiest way to do this is create a mapping array with pattern from the table. Then map the pattern to each character and print result.

 

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:

1-HOME-SWEET-HOME
MY-MISERABLE-JOB

 


Output:

1-4663-79338-4663
69-647372253-562

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10921 - Find The Telephone
 * Technique: Mapping character from an array to another.
 */

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


#define N 128


static char mappingArray[N] = "22233344455566677778889999";


static char table[N];
static char input[N];


int main(){

    /**
     * The code below fill 'A' to 'O' with appropriate values.
     * Not necessary when using mapping array.
     */
    /*
    for(int i = 0; i <= 15; ++i ){
        table[64 + i] = k;
        if(i % 3 == 0) ++k;
    }
    */


    int k = 0;

    /**
     * Map each character index to integer value from mapping array.
     */
    for(int i = 'A'; i <= 'Z'; ++i)
        table[i] = mappingArray[k++];


    /**
     * These characters don't change.
     */
    table['-'] = '-';
    table['0'] = '0';
    table['1'] = '1';


    /**
     * Take input, then iterate through each character
     * and print the character indexed value from table.
     */
    while( gets(input) ){
        for(int i = 0; input[i]; ++i)
            printf("%c", table[ input[i] ]);
        printf("\n");
    }

    return 0;
}
Advertisements

UVA Problem 10008 – What’s Cryptanalysis? Solution

UVA Problem 10008 – What’s Cryptanalysis? Solution:


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

Solving Technique:

Task for this problem is to find occurrence of each alphabetical character. Uppercase and lowercase are treated as same characters. No other characters except for upper and lower case characters must be counted.

After counting their occurrence print them in most to least order. If multiple characters have same character count then print the characters alphabetically. Ex: If E occurred 2 times, A occurred 2 times then, print A first then E.
 

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
This is a test.
Count me 1 2 3 4 5.
Wow!!!! Is this question easy?

 


Output:

S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10008 - What's Cryptanalysis
 * Technique: Counting character occurrence in string,
 *            Lexicographical / alphabetically sort characters,
 */


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


#define N 256


// Holds each character and its occurrence in string.
struct collection{
    char character;
    int occurence;
} node[26];


static char s[N];


// Sorts based on occurrence, if occurrence count is same
// then sort using lexicographical / alphabetically first character.
int cmp(collection a, collection b){

    if(a.occurence < b.occurence)
        return 0;
    else if(a.occurence > b.occurence)
        return 1;
    else
        return (a.character <= b.character) ? 1 : 0;

}



int main(){

    // O(1)
    // Represent character by its ASCII value index.
    for(int i = 'A'; i <= 'Z'; ++i)
        node[i].character = i;

    int n;

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

    while( n-- ){

        gets( s );

        // Convert string to uppercase O(n)
        for(int i = 0; s[i]; ++i){
            if( s[i] >= 'a' && s[i] <= 'z')
                s[i] = s[i] - 32;
        }


        // O(n)
        // Counting using character index
        for(int i = 0; s[i]; ++i){
            if( s[i] >= 'A' && s[i] <= 'Z' )
                ++node[ s[i] ].occurence;
        }

    }


    // Sorts occurrence most to least and in lexicographic order.
    std::sort(node + 'A', node + 'Z', cmp);


    // O(1)
    // Prints sorted occurrence most to least.
    // Also prints characters in lexicographic
    // order if two occurrence are same.
    for(int i = 'A'; i <= 'Z'; ++i){
        if(node[i].occurence)
            printf("%c %d\n", node[i].character, node[i].occurence);
    }



    return 0;
}

UVA Problem 424 – Integer Inquiry Solution

UVA Problem 424 – Integer Inquiry Solution:


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

Solving Technique:

This problem requires adding integers. The integers are very long, meaning they won’t fit even in long long. So the addition needs to be done using arrays.

It can be solved using integers arrays but my solution uses character array. Code is explained in the comments.

Similar to this problem UVA 10035 Primary Arithmetic and UVA 713 – Adding Reversed Numbers.

 

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:

123456789012345678901234567890
123456789012345678901234567890
123456789012345678901234567890
0

 


Output:

370370367037037036703703703670

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 424 - Integer Inquiry
 * Technique: Adding Multi String Integer characters column wise
 */


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

#define N 160


static char s[N][N];
static char output[N];



int main(){

    int i = 0;

    int maxlen = 0;


    // Finish taking all the inputs.
    while( gets(s[i]) ){

        // Exit for input of 0.
        if( s[i][0] == '0' && ! s[i][1] )
            break;

        int len = strlen( s[i] );

        // Get the max length to create padding.
        if( len > maxlen )
            maxlen = len;

        ++i;
    }

    // Save rows
    int rows = i;


    // Create padding for each of the strings.
    for(int j = 0; j < i; ++j){

        int temp = strlen( s[j] );

        if( temp != maxlen ){

            // Shift by this many spaces to create 0's in front.
            int padding = maxlen - temp;

            // shift by padding columns.
            for(int k = temp - 1; k >= 0; --k)
                s[j][k + padding] = s[j][k];

            // Add 0's as paddings.
            for(int k = 0; k < padding; ++k)
                s[j][k] = '0';
        }
    }


    int carry = 0, z = 0;

    for(int j = maxlen - 1; j >= 0; --j){

        int sum = 0;

        // Add values column wise.
        for(int i = 0; i < rows; ++i)
            sum += s[i][j] - '0';

        // Add if any previous  carry
        sum = sum + carry;

        // Add value to output
        output[z++] = sum % 10 + '0';

        // get the carry for adding to next column
        carry = sum / 10;

    }

    // Print if any carry first
    if(carry)
        printf("%d", carry);


    // Then print what ever character is left
    for(int i = z - 1; i >= 0; --i){
        if(output[i] >= '0' && output[i] <= '9')
            printf("%c", output[i]);
    }
    printf("\n");

    return 0;
}

UVA Problem 10851 – 2D Hieroglyphs decoder Solution

UVA Problem 10851 – 2D Hieroglyphs decoder Solution:


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

Solving Technique:

This problem may look a little hard at first but the problem could be easily reverse engineered from the problem statement. Before starting this if you are familiar with UVA PROBLEM 10878 – DECODE THE TAPE then apply that knowledge. This problem is also very similar.

It is also possible to pre calculate a pattern table based on printable ASCII character then apply a string matching algorithm ( which is harder than this ). This is a reminder for myself and anyone else who wants to implement this method.

Here \forall is called universal quantifier, so \forall can be termed as for all and \in means member of or, element of or, in.


Dissecting problem statement to create pattern generator:

H is a 2D array. It is filled following rules below. I have used H as a function to generate the 2D pattern,

H_{i,j} =     \begin{cases}       ' \backslash ' & \forall i = 0, j \in (0, 1, ..., M + 1)  \\      ' \backslash ' & \forall i = 9, j \in (0, 1, ..., M + 1)  \\      ' \backslash ' & \forall j = 0, j \in (0, 1, ..., 9)  \\      ' \backslash ' & \forall j = M + 1, i \in (0, 1, ..., 9)  \\      b(i - 1, c_{j-1}) & \forall i \in (1, 2, ..., 8) , j \in (1, ..., M)  \\    \end{cases}

Its Helper function,

b(i, c) =   \begin{cases}  ' / ' & if, \ \frac{c}{2^i} \ mod \ 2 \ == \ 0 \\  ' \backslash ' &  if, \ \frac{c}{2^i} \ mod \ 2 \ == \ 1 \\  \end{cases}

As described in the problem statement M is the length of the string and their are M + 2 columns ( from 0 to M + 1 columns ). Also there will always be 10 rows of input.

When i is 0 or, i is 9 and j is from 0 to M + 1 print backslash.
Also when j is 0 or, j is M + 1 ( last column ) and i is from 0 to 9 then print backslash.

From above it is clearly visible there are two functions. H function depends on the b function to print slashes when i is 1 to 8 and j is 1 to M ( Length of String ). This means omitting the first, last row and first, last column.

When i is 1 to 8 and j is 1 to M the output depend on b(i,c) function. Which prints a slash based on input. It checks if character ASCII decimal value divided by 2^i is even or, odd and based on that prints a slash.

Using these relations the pattern generator can be created.


Tracing the output:

It is not possible for me to show the whole string since it will be very large. I will show with String being, c[M] = ``bc" .

When, i = 1 \ and \ j = 1 the call to b(i,c) begins with parameter b(i-1, c[j - 1]) which is,

b(1-1, c[1-1]) = b(0,c[0]) = b(0, 'b')

It loops M (strings) times for each row. Which in this case is 2 times,

b(1-1, c[2-1]) = b(0, 'c')

In the b(i,c) function it checks if, character divided by 2^i is even or odd and prints slashes based on that.

for b(0,'b') it is calculated, (98 / 2^0) % 2 which is 0 so prints forward slash ‘/’.
for b(0,'c') it is calculated, (99 / 2^0)% 2 which is 1 so prints backslash ‘\’.

The b(i,c) is called M times for each row and 8 times for each column and a slash is printed based on that. The rest two times slashes are printed from the condition of H_{i,j} function.

From this relation, setting 0 for forward slashed and 1 for backward slashed the column wise string looks like its in binary format. Where the top row is Least significant bit (LSB) and bottom row is Most significant bit (MSB). In case of ‘b’ character only first column shown from the above example string,

row sign binary value
0 / 0 0
1 \ 1 2
2 / 0 0
3 / 0 0
4 / 0 0
5 \ 1 32
6 \ 1 64
7 / 0 0

Their sum is = 2 + 32 + 64 = 98 or, converting the binary to decimal gives a value of 98 which is the ASCII decimal value of ‘b’. Similarly, more characters are calculated if there are more columns.


Shortcut Technique:

Basically first, last row and column are useless. A character is decoded based on each column. A forward slash means 0 and a backslash mean 1. Just apply bit wise shift for each row in a column and add the value when backslash is found. From that value print is equivalent ASCII character.

 

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:

2
///////////
/\/\/\/\/\/
//\\//\\///
////\\\\///
////////\\/
///////////
/\\\\\\\\\/
/\\\\\\\\\/
///////////
///////////

///////////////////////////////////////
//\///\/\\/\//\\/\//\/\\/\/\/\\/\/\//\/
///////\////\/\/\//////\//\////\/\/////
/\//\\\\///\\//\\/\\//\//\\//\///\/\\//
/\//\\//\///\////\\\//////\//\////\\\//
//////\\//////\/\//////\/\/////\/\/////
///\//////\//\///////\//\///\//////////
/\\/\\\\\\/\\/\\\\\\\/\\/\\\/\\\\\\\\\/
///////////////////////////////////////
///////////////////////////////////////

 


Output:

abcdefghi
LA LLUVIA EN SEVILLA ES UNA MARAVILLA

Critical Input Generator:

Warning!!!
This is not the solution just input generator for the problem. The Solution code is below this code.

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10851 - 2D Hieroglyphs Decoder Pattern / Input Generator
 */

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

//static char c[] = "bc";
//static char c[] = "abcdefghi";
static char c[] = "LA LLUVIA EN SEVILLA ES UNA MARAVILLA";


void b(int i, char ch){
    // May be do a bitwise shift since power of 2
    if( (ch / (long long) pow(2, i) ) % 2 == 0 )
        printf("/");
    else
        printf("\\");
}


void H(int row, int M){
    // String length is M and column is M + 2 so from 0 to M - 1
    M = M + 2;

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

        // This can be moved outside loop with little adjustment
        if(i == 0 || i == row - 1){
            for(int j = 0; j < M; ++j)
                printf("/");
        }

        else{
            for(int j = 0; j < M; ++j){
                // Since M = M + 2 so j is j == (M - 1) = (M + 2 - 1) = (M + 1)
                if(j == 0 || j == M - 1)
                    printf("/");
                else
                    b(i - 1, c[j - 1]);
            }
        }

        printf("\n");
    }

}


int main(){

    H(10, strlen(c) );

    return 0;
}

Solution Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10851 - 2D Hieroglyphs Decoder
 * Technique: Binary to Decimal, 2D row wise calculation.
 */

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

static char c[10][80];

int main(){

    int n, i;

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

    while( n-- ){

        /**
         * Reset each of the strings ignoring first and last row.
         */
        for(i = 1; i < 9; ++i)
            memset(c[i], 0, sizeof c[i]);


        /**
         * Reuse i for taking string inputs.
         */
        i = 0;


        /**
         * Take input of 10 rows.
         * Another logic is to discard first and last line when taking input.
         * But this method is easier to code.
         */
        while(gets(c[i]) && strlen(c[i]))
            ++i;


        /**
         * Take count of the column.
         * Since input is a rectangle so any column length will work.
         */
        int cols = strlen(c[0]);


        /**
         * Ignore last column.
         * Also last row.
         */
        cols = cols - 1;
        i = i - 1;


        /**
         * k represents columns and j represents rows.
         * k starts from 1 ignoring first column.
         */
        for(int k = 1; k < cols; ++k){

            // Reset for each column.
            int sum = 0;
            int shift = 1;

            /**
             * Ignoring the first and last character.
             * i starts from 1 ignoring first row.
             */
            for(int j = 1; j < i; ++j){

                // Double slash means (for this case) in binary 1 and add that value.
                // Otherwise its zero and no need to calculate in that case.
                if( c[j][k] == '\\' )
                    sum = sum + shift;

                // Bitwise shift left once for each column.
                shift = shift << 1;
            }

            // Print character wise or use string then print outside this loop.
            printf("%c", sum);
        }

        printf("\n");

    }

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