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

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