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

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

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print:

Code Explanation:

This code is bit complex and will require knowledge on:

  1. Struct
  2. Linked list
  3. Queue
  4. Stack
  5. Binary Tree ( check this and this too  )

Input Format:

Level Order tree input style
Level Order tree input style
binary Tree Graph sample Input for the console picture shown above
binary Tree Graph sample Input for the console picture shown above

Code:

/*
 * Author: Quickgrid
 * Code: Tree creation, traversal in array & linked list ( inorder/preorder/postorder/levelorder )
 * Description:
 */

#include <stdio.h>

#define size 1000   /* used this for queue array */

struct tree{    /* binary tree structure */
    char data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree node;

struct stack{   /* linear/singly linked list stack to hold tree type data */
    node *nodedata;
    struct stack *next;
};
typedef struct stack vertex;

node* q[size];  /* here our array is node data type that we defined above */
int f = 0, r = 0;
vertex *front = NULL, *rear = NULL;
node *root = NULL;

void enq(node *root){   /* circular queue array modular arithmetic */
    int s = (r+1) % (size+1); /* +1 means we don't use 1 box of the array */
    if(f == s){
        printf("Queue Full.\n");
        return;
    }
    q[s] = root; /* root is node type we put it in our node array */
    r = s;  /* s is temporary variable */
}

node *deq(){
    if(f==r){
        printf("Queue Empty.\n");
        return NULL;
    }
    f = (f+1)%(size+1);
    node *temp = q[f]; /* get the last element of the queue to return for further operations */
    q[f] = 0;
    return temp;
}

void levelOrderArray(node *root){
    enq(root);  /* here we enqueue the root or the node that we want to star from */
    while(f!=r){ /* check if our queue is not empty */
        node *v = deq(); /* dequeue one item */
        printf("%c ", v->data);
        if(v->left!=NULL){ /* check if left branch of tree exists */
           enq(v->left); /* send the left node to queue */
        }
        if(v->right!=NULL){ /* check if right branch of tree exists */
            enq(v->right); /* send the right node to queue */
        }
    }
}

void enqueue(node *root){   /* enqueue function for our stack in linked list */
    if(front == NULL){
        front = new vertex();
        front->nodedata = root;
        front->next = NULL;
        rear = front;
    }else{
        vertex *temp = new vertex();
        temp->nodedata = root;
        temp->next = NULL;
        rear->next = temp;
        rear = temp;
    }
}

vertex *dequeue(){
    if(front == NULL){
        printf("queue empty.\n");
        return front;
    }
    vertex *temp,*tmp = front;
    front = front->next;
    delete temp;
    return tmp;
}

void levelorder (node *root){
    enqueue(root);
    while ( front != NULL ){
        vertex *v = dequeue();  /* we dequeue one vertex type data from our vertex stack */
        if(v!=NULL){
            printf("%c",v->nodedata->data);

            if (v->nodedata->left != NULL){ /* nodedata is our data part which holds node type data */
                enqueue(v->nodedata->left);
            }
            if (v->nodedata->right != NULL){
                enqueue(v->nodedata->right);
            }
        }
    }
}

int treeHeight(node *root){
    if(root == NULL){
        return 0;
    }
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);

    if(leftHeight > rightHeight){
        return leftHeight+1;
    }else{
        return rightHeight+1;
    }
}

void printGivenLevel(node *root, int level){
    if(root == NULL){
        return;
    }
    if(level == 1){
        printf("%c ", root->data);
    }else if(level > 1){
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}

void createBinaryTree (node *root)
{
    char ans;

    fflush(stdout);
    printf("%c has any left child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create left side of a tree node */
    {
        root->left = new node ();
        root->left->left = NULL;
        root->left->right = NULL;
        fflush(stdout);
        printf("Enter left data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->left->data);
        createBinaryTree (root->left);  /* recursive call with created node as root to check if it has left and right */
    }

    fflush(stdout);
    printf("%c has any right child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create right side of a tree node */
    {
        root->right = new node ();
        root->right->left = NULL;
        root->right->right = NULL;
        fflush(stdout);
        printf("Enter right data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->right->data);
        createBinaryTree (root->right);
    }
}

void postOrder(node *root){
    if(root->left!=NULL){
        postOrder(root->left);
    }
    if(root->right!=NULL){
        postOrder(root->right);
    }
    printf("%c ", root->data);
}

void preOrder(node *root){
    printf("%c ", root->data);
    if(root->left!=NULL){   /* check if left side of that node exist */
        preOrder(root->left);   /* recursive call of preorder using this node as the root */
    }
    if(root->right!=NULL){
        preOrder(root->right);
    }
}

void inOrder(node *root){
    if(root->left!=NULL){
        inOrder(root->left);
    }
    printf("%c ", root->data);
    if(root->right!=NULL){
        inOrder(root->right);
    }
}

int main ()
{
    char ans;
    fflush(stdout);
    printf("Do u want to create a tree: ");
    fflush(stdin);
    ans = getchar();

    root = new node ();
    fflush(stdout);
    printf("Enter root of tree: ");
    fflush(stdin);
    scanf("%c",&root->data);
    createBinaryTree(root);

    int height = treeHeight(root);
    printf("\nTree Height: %d", height);

    printf("\nLevel order Linked List: ");
    levelorder(root);   /* Instead of sending root we can send another node to level order from that node */
    printf("\nLevel order Array: ");
    levelOrderArray(root);
    printf("\nPre order : ");
    preOrder(root);
    printf("\nIn order : ");
    inOrder(root);
    printf("\nPost order : ");
    postOrder(root);

    printf("\nEnter level to print:");
    int level;
    scanf("%d", &level);
    if(level >= height || level < 1){
        printf("\nGiven level doesn't exist.");
    }else{
        printf("Level %d: ", level);
        printGivenLevel(root, level);
        printf("\n");
    }
    return 0;
}