UVA Problem 10924 – Prime Words Solution

UVA Problem 10924 – Prime Words Solution:


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

Solving Technique:

This problem is easy we just need to read it carefully.

The problem assigns values for 1 to 26 for (a-z) and 27 – 52 for (A-Z). The input is a stringWe are asked to find the sum of every character with given value and check if the sum is a prime number or not.  

Summing is actually easy. For lower case when we sum, we just subtract the character from ASCII value of a or the ‘a’ character. This way we get 1 to 25 for ( a to z ). Since the number that was assigned was 1 more, so we add 1 to every value in loop. We do the same thing for upper case letters ( subtract ‘A’ from each character ). So we get 0 to 25 again. This time we add 27 to every value in loop so we get 27 to 52 for ( A to Z ).

One important thing to note is although 1 is not a prime. In this problem it is specified that it is prime. We output according to given specification.  So if the sum of all given word is 1 then the output is prime. Ex, a ( since a is 1 ).

The given word length is 1 to 20. So an array of 21 is enough. We should check for EOF to terminate the program.

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.


Critical Inputs:

UFRN
contest
AcM
a

Output:

It is a prime word.
It is not a prime word.
It is not a prime word.
It is a prime word.

Code (using lookup table, Sieve of Eratosthenes):

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

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

/**
 * Since there is max of 20 characters in a single line
 * Calculating with biggest value 'Z' gives a max of 1040
 */
#define N 1041

static int table[128];
static unsigned primes[N];

void PreSum(){
    register unsigned i, j = 1;

    /**
     * Set 1 to 26 for 'a' to 'z'
     */
    for (i = 'a'; i <= 'z'; ++i, ++j)
        table[i] = j;

    /**
     * Set 27 to 52 for 'a' to 'z'
     */
    for (i = 'A'; i <= 'Z'; ++i, ++j)
        table[i] = j;
}

void SieveOfEratosthenes(){
    register unsigned i, j;

    /**
     * For this problem though 0 and 1 are primes
     */
    for (i = 0; i < N; ++i)
        primes[i] = 1;

    unsigned len = sqrt(N);

    for (i = 2; i <= len; ++i){
        if (primes[i]){
            for (j = i * i; j <= N; j += i)
                primes[j] = 0;
        }
    }
}

int main(){
    /**
     * Pre calculate character value table
     * Pre calculate prime values using Sieve of Eratosthenes
     */
    PreSum();
    SieveOfEratosthenes();

    char s[32];
    register unsigned i;

	while (gets(s)){
        unsigned sum = 0;

        /**
         * Get character value from pre calculated character value table and sum them
         */
        for (i = 0; s[i]; ++i)
            sum += table[s[i]];

        /**
         * Get primality from pre calculated prime table
         */
        if (primes[sum])
            printf("It is a prime word.\n");
        else
            printf("It is not a prime word.\n");
	}
	return 0;
}

Code (without using table):

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

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

static char s[32];

int main(){
    while (gets(s)){
        unsigned int i, sum = 0;

        for (i = 0; s[i]; ++i){
            if (s[i] >= 'a' && s[i] <= 'z')
                sum += s[i]-'a'+1;
            else
                sum += s[i]-'A'+27;
        }

        if (sum <= 2)
            printf("It is a prime word.\n");
        else if (sum % 2 == 0)
            printf("It is not a prime word.\n");
        else{
            unsigned int prime = 1, len = sqrt(sum);
            for(i = 3; i <= len; i += 2){
                if(sum % i == 0){
                    printf("It is not a prime word.\n");
                    prime = 0;
                    break;
                }
            }
            if (prime)
                printf("It is a prime word.\n");
        }
    }
    return 0;
}
Advertisements

UVA Problem 11636 – Hello World! Solution

UVA Problem 11636 – Hello World! Solution:


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

Solving Technique:

Here i have given Three solution one is Hybrid ( pre-calculated values with little calculations, Rank 1821 ) , another is with pre-caculated values stored in table ( see Memoization and Look up table ) ,last one is pure calculation. For this problem i have found out all answer combinations. So you can use your logic to get your code faster.

The problem requires us to find minimum number of copy commands to reach input lines.

For example, if there is 1 line and we copy whats on-screen 4 times we get 16 lines. How?

1 line copy paste 2 lines (since there was 1 line and we copied 1 more line)
2 line copy paste 4 lines (since there was 2 line and we copied 2 more line)
4 line copy paste 8 lines (since there was 4 line and we copied 4 more line)
8 line copy paste 16 lines (since there was 8 line and we copied 8 more line)

As we can what we copy is twice ( 2 times ) the amount of original.

Now we can use this knowledge to find the copy commands required. We can just loop until we find that our line number exceeds the given line. Now as many times as we looped is the copy command required.

Because we can copy 11 lines, 10 lines or 9 lines in 4 commands. We weren’t given any restriction on this. Just looping until our copy lines for the loop exceed the given line is enough.

Also Critical thing is input can be 0, 1 both for these the output is 0. For 1 the answer is 0 because. There is already a line so it takes 0 command to get 1 line.

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.


Critical Inputs:

21
99
0
1
1001
101
11
-1

Output:

Case 1: 5
Case 2: 7
Case 3: 0
Case 4: 0
Case 5: 10
Case 6: 7
Case 7: 4

Code Easier:

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

#include<stdio.h>

int main(){
    int n;
    register unsigned c = 1;
    while(scanf("%d", &n) && n>-1){
        register unsigned i = 1, p = 0;
        while(i < n){
            /*
             * In the equation 2^p > n, for which value is greater than input, Here p is the answer
             */
            i <<= 1;
            ++p;
        }
        printf("Case %u: %u\n", c, p);
        ++c;
    }
    return 0;
}

Faster Solution ( Rank: 1821, Run time: 9 ms  ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */
#include<stdio.h>
int main(){
    int n;
    register unsigned int c = 1;
	while(scanf("%d", &n) && n>-1){
        if(n>1){
            if(n > 8192)
                printf("Case %u: 14\n", c);
            else if(n >= 4097)
                printf("Case %u: 13\n", c);
            else if(n >= 2049)
                printf("Case %u: 12\n", c);
            else if(n >= 1025)
                printf("Case %u: 11\n", c);
            else{
                register unsigned int i = 1, lines = 1;
                for(; i<=n; ++i){
                    lines <<= 1;
                    if(lines >= n){
                        break;
                    }
                }
                printf("Case %u: %u\n", c, i);
            }
        }else printf("Case %u: 0\n", c);
        ++c;
	}
	return 0;
}

Another Solution ( with Look Up Table ):

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

#include<stdio.h>
static unsigned arr[10010];

void precalculate(){
    register unsigned n = 10001;
    arr[0] = 0;
    arr[1] = 0;
    arr[2] = 1;
    arr[3] = 2;
    arr[4] = 2;
    arr[5] = 3;
    arr[6] = 3;
    arr[7] = 3;
    arr[8] = 3;

    /**
     * If you look carefully there is a nice pattern here
     * This code can be shorted with a nested loop
     * 2^N <= Loop <= 2^(N-1) + 1
     */
    for(; n >= 8193; --n)
        arr[n] = 14;
    for(; n >= 4097; --n)
        arr[n] = 13;
    for(; n >= 2049; --n)
        arr[n] = 12;
    for(; n >= 1025; --n)
        arr[n] = 11;
    for(; n >=  513; --n)
        arr[n] = 10;
    for(; n >=  257; --n)
        arr[n] = 9;
    for(; n >=  129; --n)
        arr[n] = 8;
    for(; n >=   65; --n)
        arr[n] = 7;
    for(; n >=   33; --n)
        arr[n] = 6;
    for(; n >=   17; --n)
        arr[n] = 5;
    for(; n >=    9; --n)
        arr[n] = 4;
}

int main(){
    precalculate();
    int n;
    register unsigned c = 1;

    while (scanf("%d", &n) && n > -1){
        printf("Case %u: %u\n", c, arr[n]);
        ++c;
    }

    return 0;
}

UVA Problem 1124 – Celebrity jeopardy Solution

UVA Problem 1124 – Celebrity jeopardy Solution:


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

Solving Technique:

Another super easy problem. The instructions on the top are just to distract us or make us thinks it is a tough problem.

I have made a video tutorial ( English ) for this code. I will also upload a Bengali version soon.

Problem statement requires us to find the equation whose transformation into the desired answer requires the least effort. So the least effort for a celebrity is print the equation that was given.

So for this problem we just input a string and print it. That all.

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:

Y = 3 
X=9

Output:

Y = 3 
X=9

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */
#include<stdio.h>
int main(){
    char s[128];
    while(gets(s)){
        puts(s);
    }
    return 0;
}

UVA Problem 113 – Power of Cryptography Solution

UVA Problem 113 – Power of Cryptography Solution:


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

Solving Technique:

This is a very easy mathematical problem. The formula is given. kn = p. We can solve this with taking ln on each sides and calculating for k using k = e(ln(p)/n). But the formula below is easier.

Simplify kn = p,

kn = p
(kn)(1/n) = p(1/n)
k = p(1/n)       /* k = pow(p,1/n) */

or, just using power formula below. We are asked to find the value of k given n and p. Also The formula for calculating k is given n√p.

For this problem taking n and p is double is enough. Also for this problem there is no digits after decimal. For c double printf to discard values after decimal point we can use,

%.0lf

Also we should keep scanning until EOF is encountered.

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:

2
16
3
27
7
4357186184021382204544

Output:

4
3
1234

Code:

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

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

int main(){
    double n,p;
    while (scanf("%lf%lf", &n, &p) == 2)
        printf("%.0lf\n", pow(p, 1 / n));
    return 0;
}