UVA Problem 12854 – Automated Checking Machine Solution

UVA Problem 12854 – Automated Checking Machine Solution:


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

Solving Technique:

For This problem I tried many times but best I could get was rank 116 and run time 0.009 s ( 9 ms ). This is really bad for a very simple code.

The logic is simple we are given two strings ( or, 10 integers ) . If the character in the same index / position of the two strings are different we print Y. Otherwise if the characters are same we print N.

Since I know that there will 5 and 5 total of 10 characters each time. So I used integer to take input.

Now I used XOR between to integers because applying XOR to two integers if they are equal then we get 0. Otherwise we get a 1. XOR table,

a b a^b
0 0  0
0 1  1
1 0  1
1 1  0

So that is what I need if they are same i get 0 and else I get 1. Using this logic I check all 10 values. Then use ternary operation to print Y or, N.

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.


Input:

1 1 1 1 1
0 0 0 0 0
1 1 0 1 0
0 0 1 0 1
1 0 0 1 0
1 0 1 1 0

Output:

Y
Y
N

Code:

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link https://quickgrid.wordpress.com
 * Problem: UVA 12854 - Automated Checking Machine
 */

#include<stdio.h>
int main(){
    register unsigned int a,b,c,d,e,f,g,h,i,j;
	while (scanf("%u%u%u%u%u%u%u%u%u%u", &a, &b, &c, &d, &e, &f, &g, &h, &i, &j) == 10){
        (a ^ f && b ^ g && c ^ h && d ^ i && e ^ j) ? printf("Y\n"): printf("N\n");
	}
	return 0;
}

UVA Problem 12708 – GCD The Largest Solution

UVA Problem 12708 – GCD The Largest Solution:


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

Solving Technique:

This problem can be solved just by looking at the output. But we must understand the problem.

For this problem we are given an input N and expected find GCD of all pairs of numbers between 1 to N. If we look at the given table we can see that we can’t understand the table :).

The table shows pairs of numbers between 1 to N. The First COLUMN represents N ( the input ) and the First ROW represents number from 1 to N-1. Why? because the first column already represents N. We can’t make pair of the same number.

This way if we draw the table for bigger number we can see an important pattern that is the biggest GCD of 1 to N is FLOOR of N/2 ( N divided by two ).

One more thing keep an eye on the range 2 <= N <= 10^18. I didn’t look at it ( used unsigned int ) and ate a WA. I hope you know the data type to handle this range.

Lets get coding :).

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:

6
0
1
2
3
4
5

Output:

0
0
1
1
2
2

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: 12708 - GCD The Largest
 */
#include<stdio.h>
int main(){
	unsigned long long n,m;
	scanf("%llu", &n);
	while(n--){
        scanf("%llu", &m);
        printf("%llu\n", m>>1);
	}
	return 0;
}

Another One(Faster):

using c++,

#include<iostream>
int main(){
    std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	register unsigned int n;
	unsigned long ago;
	std::cin >> n;
	while(n--){
        std::cin >> ago;
        std::cout << (ago>>1) << "\n";
	}
	return 0;
}

UVA Problem 10935 – Throwing cards away I Solution

UVA Problem 10935 – Throwing cards away I Solution:


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

Solving Technique:

It is possible possible to solve this problem in many ways. Using STL queue is one way. But I try to avoid built-in functions just so I can make my base stronger and learn new things. Here I have written my own queue implementation.

The problem says we have a deck of card which is ordered 1 to n. n is the input. Ex, if 7 is input then we have 1,2,3,4,5,6,7 cards on deck.

Next, it says discard the top card, so card after him is now topmost. Then move the topmost card of the deck to the end of the deck. Keep continuing this until two card are left of deck. The process happens like this, if n = 5 is given,

1 2 3 4 5 /* Initial array enqueued 1 through 5 */

/* First Iteration */
2 3 4 5   /* 1 is discarded and printed */
3 4 5 2   /* 2 is moved to end of queue */

/* Next Iteration */
4 5 2    /* 3 discarded and printed */
5 2 4    /* 4 moved to end of queue */

/* Next Iteration */
2 4     /* 5 discarded and printed */
4 2     /* 4 is also discarded since we want to find the last card and so we print the last card reaming on deck which is 2 */

Notice even though we discard 1 card we move the other one to the end of the deck. So the deck size is decreasing by one ( don’t get confused here ).

Since one card is thrown away and another is moved to the end i thought hey its a queue. Why? queue has a function called dequeue which discards the topmost ( or actually the element in front ). Now another card is moved to end of the deck. Queue has a similar function called enqueue which adds an element to the end of the array or queue. Also since Queue is a FIFO ( FIRST IN FIRST OUT ) data structure. So what is on the front of deck is processed first and that is what we need.

Think of it like a game where each cards are aligned horizontally and each card is a person. Now we tell the player who is in front of the line to move away so the player that was after him is in front of the line. This time we tell the player to move to the end of line. We continue this discard and adding the next one to the end  until there are only two player left. So of these two player the last player is the remaining cards and the players that were moved from line are the discarded cards.

Our input terminates with 0 ( zero ). I have explained the code below with comments.

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
19
10
6
0

Output:

Discarded cards: 1, 3, 5, 7, 4, 2
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8
Remaining card: 4
Discarded cards: 1, 3, 5, 2, 6
Remaining card: 4

Code:

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

#include<stdio.h>
#define size 128

/*
 * unsigned since no item in our array is negative
 */
unsigned a[size], f = 0, r = 0;

void enqueue(unsigned k){
    /*
     * get a valid index in circular queue array
     */
    unsigned s = (r + 1) % (size + 1);

    /*
     * if true queue full, this check is for safety and can be deleted
     */
    if (f == s)
        return;

    /*
     * set the last element to given card
     */
    a[s] = k;
    /*
     * update the rear position marker
     */
    r = s;
}

unsigned dequeue(){
    /*
     * if true then queue empty, this check is for safety and can be deleted
     */
    if (f == r)
        return 0;

    /*
     * move the front marker one position in circular queue array
     */
    f = (f + 1) % (size + 1);
    /*
     * keep the value of last card for returning
     */
    unsigned k = a[f];
    a[f] = 0;
    return k;
}

int main(){
    register unsigned n, i;

    while (scanf("%u", &n) && n){
        /*
         * since there is one card there is no discarded card
         */
        if (n == 1){
            printf("Discarded cards:\n");
            printf("Remaining card: 1\n");
            continue;
        }

        f = 0, r = 0;
        for (i = 1; i <= n; ++i){
            /*
             * it says 1 to n cards on deck so i enqueue all cards serially
             */
            enqueue(i);
        }

        printf("Discarded cards: ");
        /*
         * stop when 2 cards on deck
         */
        while (f + 2 != r){
            printf("%u, ", dequeue());
            unsigned k = dequeue();
            enqueue(k);
        }

        /*
         * get position of last discardable card
         */
        f = (f + 1) % (size + 1);

        /*
         * print the last discardable card
         */
        printf("%u\n", a[f]);
        /*
         * now print the last remaining card on deck
         */
        printf("Remaining card: %u\n", a[r]);
    }
    return 0;
}

UVA Problem 10878 – Decode the tape Solution

UVA Problem 10878 – Decode the tape Solution:


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

Solving Technique:

The problem may seem easy to some and maybe hard for some. There are multiple ways of solving this. Please take a look at this if don’t have a good understanding if binary numbers. Also learn Bitwise operations. Do not print a new line for this problem.

At first glance it doesn’t make sense. But trying to match characters we see a pattern. Like whenever we see

|  o  .   |

we see there is a space. Each line represents a character we can find this easily by counting characters in the given output and counting lines on input tape. This we can match every character to its corresponding line on the tape. But in the last line we see there is an extra line on the ( not the blank line ) tape. That represents the newline.

Now there are only two types of data on the tape a space character and a hole ( o character ). One example for problem like this when writing in the exams we fill in ID box with pencils by circling the numbers that match our id number.

So since there are only two types ( Forget . and | ) of data it is either 0 or 1 meaning binary. So now when we assign a value to each binary digits we can see that when we add values for 1 we get ASCII value of the character.  

Now that we understand the problem we can solve this in different ways. One approach can be for every loop we can check the value of that character. It is possible since the tape length is always same. if it is 1 we add the corresponding decimal number for that binary digit. Ex:

/* I skip s[0] because it is not a space or o character in tape */
if(s[1] == 'o') sum = sum + 128;
if(s[2] == 'o') sum = sum + 64;
/* keep going like this for each hole or space character */

My approach is bit shifting. By bit shifting we get the same result. Since the string consisting of ( space and hole ) is always 8 characters long. Starting from left we can assign values by increasing power by 1 for each value to left.

128  64  32  16  8   4   2   1
2^7 2^6 2^5 2^4 2^3 2^2 2^1 2^0
 1   1   1   1   1   1   1   1

If I search the string from left then I need set bit to 128 and shift right ( making them smaller for each values to right ). That what I did here. So here values are decreasing right to left. 

Another approach is start from the end of string and set the bit to 1. Now we shift bits to left every time we find a space or a hole. So, here values are increasing left to right.

for(i = strlen(s) - 1; i >= 0; --i){
        if(s[i] == ' '){
            bit <<= 1;
        }else if(s[i] == 'o'){
            sum += bit;
            bit <<= 1;
        }
}

Important:  The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

___________
| o   .  o|
|  o  .   |
| ooo .  o|
| ooo .o o|
| oo o.  o|
| oo  . oo|
| oo o. oo|
|  o  .   |
| oo  . o |
| ooo . o |
| oo o.ooo|
| ooo .ooo|
| oo o.oo |
|  o  .   |
| oo  .oo |
| oo o.ooo|
| oooo.   |
|  o  .   |
| oo o. o |
| ooo .o o|
| oo o.o o|
| ooo .   |
| ooo . oo|
|  o  .   |
| oo o.ooo|
| ooo .oo |
| oo  .o o|
| ooo . o |
|  o  .   |
| ooo .o  |
| oo o.   |
| oo  .o o|
|  o  .   |
| oo o.o  |
| oo  .  o|
| oooo. o |
| oooo.  o|
|  o  .   |
| oo  .o  |
| oo o.ooo|
| oo  .ooo|
|  o o.oo |
|    o. o |
___________

Output:

A quick brown fox jumps over the lazy dog.

Code:

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

#include<stdio.h>

static char s[64];

int main(){
    register unsigned int i;
    unsigned sum, found;

    while(gets(s)){
        unsigned int bit = 128;     /* Since the binary form is 8 characters long ( not including . or | ) 2^7 = 128 ( 7 but not 8 starts from 0. 2^0....2^7 total 8 digits ) we keep left shifting and adding only if we find a hole */

        i = sum = found = 0;
        if(s[i] != '|') continue;   /* We don't want to print anything for lines not starting with | */

        for(; s[i]; ++i){
            if(s[i] == ' ')
                bit >>= 1;          /* keep shifting bits right ( makes them smaller. Ex, 128 = 2^7. So, 128 >> 1 = 64, 2^7 >> 1 = 2^6 = 64 ) OR, you can shift bits to left make them bigger but then you have search the string in reverse order */
            else if(s[i] == 'o'){
                sum += bit;         /* Add the bits where we find a hole */
                bit >>= 1;
            }
        }

        printf("%c", sum);          /* Print the sum. No need to print newline. The last line of tape represents a newline character |    o. o | */
    }
    return 0;
}

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

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

UVA Problem 12461 ( Airplane ) Solution

UVA Problem 12461 ( Airplane ) Solution:


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

Solving Technique:

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

Just look at the output. That’s all if you just want the answer. No need to see the code 🙂

Also take a look at probability.

If you want to understand the problem:

Our input is n (  The number of passenger on-board). It says that n people board an airplane with n seats. Meaning if 6 people board the plane there are 6 seats.

So, Now it says First passenger lost ticket and he sits in a random seat. Also Each subsequent passenger sits in his own seat if it’s available or takes a random unoccupied seat if it’s not.

Now it asks for the probability that nth passengers seat is occupied. The nth passenger is obviously the last passenger. So if 5 people board a plane, there are 5 seats then the nth passenger is 5. There is only 1 passenger is not seated at a time.

Point to note is all other passengers except nth passenger are seated after taking seats of their choice. So when the last passenger tries to seat there are two things that he may find. Either, his seat is occupied or, it is empty. So there is total two outcomes. 

So the probability of finding seat occupied is = desired outcome count / total outcomes. Only one of two things happen at a time. Another passenger can seat in nth passenger seat or not seat there. There is 50% chance of finding the seat occupied.

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
3
4
9
0

Output:

1/2
1/2
1/2
1/2

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */
#include<stdio.h>
int main(){
	unsigned int n;
	while(scanf("%u", &n) == 1 && n!=0){
        printf("1/2\n");
	}
	return 0;
}