UVA Problem 612 – DNA Sorting Solution

UVA Problem 612 – DNA Sorting Solution:


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

Solving Technique:

The best solution for this problem took 0.020 s. Mine took 0.142 s. There is an efficient algorithm to solve this problem. My approach is brute force, check all possible combination and count. Besides solving the problem another goal was implement some less used techniques/concepts.

So the problem basically requires us to sort and print strings based on sortedness. The way to calculate this is,

  1. The way to calculate this sortness is to take a string and compare each characters to its right.
  2. If the character on the right are smaller than the current character we increase the inversion count.
  3. The greater the count the less sorted ( confused!! ) a string is. ( Please do this with pen and paper )

Another thing to note is that if inversion count for multiple string is same then we should print the string that was given to us first. Last thing is print a blank line after each test case.

Now this code may look confusing,

char **s = new char*[t+1];

It is a way to declare an array of strings in C. The [t+1] initializes the string count. We need use a for loop to initialize string size for each strings. That is,

s[i] = new char[w+1];

Here s[i] is a string. We allocate memory for it using new char[w+1].

Here I used bubble sort to sort the strings. At first i tried selection sort and failed miserably because it doesn’t maintain the relative ordering of the strings. So using the sort I am sorting in ascending order. Also sort the inversion count array since it is mapped to strings array. Swap is a built-in function.

std::swap(inv[j], inv[j+1]); /* Swap the inversion count */
std::swap(s[j], s[j+1]);

Now that you understand the problem time to go write a better solution :).

Update (Added Insertion Sort):

I have added insertion sort for this code. Any stable sort such as insertion, merge sort etc should also work.
Just copy the code below and replace the bubble sort marked portion of code with this insertion sort code. It runs a bit faster than bubble sort. Also don’t forget to add include cstring header file.

/*
 * Insertion Sort
 */
unsigned key;
int q;
char *strkey = new char[w + 1];
for(i = 1; i < t; ++i){
    key = inv[i];
    strcpy(strkey, s[i]);
    q = i - 1;
    while(q >= 0 && inv[q] > key){
        inv[q + 1] = inv[q];
        strcpy(s[q + 1], s[q]);
        --q;
    }
    inv[q + 1] = key;
    strcpy(s[q + 1], strkey);
}

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

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Output:

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

Code ( Using Bubble Sort ):

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 * Problem UVA 612 (DNA Sorting)
 */

#include<cstdio>
#include<iostream>

int main(){
    register unsigned n,i,j,k;
    unsigned blank = 0;

    scanf("%u", &n);
    while (n--){
        unsigned w,t;
        scanf("%u%u", &w, &t);

        /* Array of strings, initialize element count */
        char **s = new char *[t + 1];
        /* Mapping array for sortedness count */
        unsigned *inv = new unsigned[t + 1];

        for (i = 0; i < t; ++i){
            /* Initialize size of each string in array */
            s[i] = new char[w + 1];
            scanf("%s", s[i]);
            inv[i] = j = 0;
            for (; j < w; ++j){
                for (k = j + 1; k < w; ++k){
                    if (s[i][j] > s[i][k])
                        /* Count sortedness, number of inversions */
                        ++inv[i];
                }
            }
        }

        /*
         * Bubble sort
         * Any stable sort should be able to sort it correctly e.g. insertion sort, merge sort
         */
        for (i = 0; i < t - 1; ++i){
            for (j = 0; j < t - i - 1; ++j){
                if (inv[j] > inv[j+1]){
                    /* Swap the inversion count */
                    std::swap(inv[j], inv[j+1]);
                    /* Swap the strings */
                    std::swap(s[j], s[j+1]);
                }
            }
        }

        /* Print a blank line for consecutive test cases */
        if (blank) printf("\n");
        blank = 1;

        for (i = 0; i < t; ++i)
            printf("%s\n", s[i]);
    }
    return 0;
}

UVA Problem 10929 – You can say 11 Solution

UVA Problem 10929 – You can say 11 Solution:


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

Solving Technique:

For this problem use a string to handle input, even unsigned long long can’t hold a large number containing 1000 digits. 

Found the logic for this code here on Algorithmist. Another way to solve this problems explained there.

We can check if a large number is divisible by another number by subtracting the sum of even index number from odd index numbers. For example,

if, ABCD, A-B+C-D % N == 0, then the number is divisible by N
if, 2937, 2-9+3-7 % 11 == -11 % 11 = 0, So, 2937 is divisible by 11

The input may have leading zeros.

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:

112233
30800
2937
323455693
5038297
112234
0

Output:

112233 is a multiple of 11.
30800 is a multiple of 11.
2937 is a multiple of 11.
323455693 is a multiple of 11.
5038297 is a multiple of 11.
112234 is not a multiple of 11.

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 10929 ( You can say 11 )
 */

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

static char s[1024];

int main(){
    unsigned i;

    while(gets(s)){
        unsigned len = strlen(s);
        if(s[0] == '0' && len == 1)
            return 0;

        int sum = 0;
        for(i = 0; i < len; i += 2)
            sum += s[i] - '0';

        for(i = 1; i < len; i += 2)
            sum -= s[i] - '0';

        printf(sum % 11 ? "%s is not a multiple of 11.\n" : "%s is a multiple of 11.\n", s);
    }
    return 0;
}

UVA Problem 100 – The 3n + 1 problem Solution

UVA Problem 100 – The 3n + 1 problem Solution:


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

Solving Technique:

This problem is not for beginners. Due to a simple logical error I failed and failed again.

Before proceeding to understand my solution please check Memoization, Lookup Table, Recursion, Dynamic Programming, Bitwise Operations. Also you may check Algorithmist Solution and Collatz Conjecture. Learned this solution technique is from here.

For this problem we are given two numbers. We need cycle from and including the smaller number to and including the bigger number.

Basically we are to cycle through the given range and find the maximum cycle length among all numbers in the given range.

Here i have used a lookup table to store already calculated cycle lengths. This dramatically decreases running time. Without lookup table my first solution took 0.552 s but when i applied memoization ( this solution ) took only 0.035 s.

0.552 > 0.035 /* See the speed difference */

Another thing is when the number is ODD we need to calculate 3*n+1. But when we calculate 3*n+1 for any ODD number the ODD number becomes EVEN. Now we can divide by 2 in same step since it becomes EVEN. So here i performed 2 steps in the ODD checking code.


 

n = 3, 3*n+1 = 10 /* So calculating 3n+1 for odd number is always even */
n = 7, 3*n+1 = 22 /* Since it becomes even we can perform n/2 in same step */

 

Also another thing to note is that i used,

n >> 1 /* Which does the same thing as n/2 but Faster */

 

So here I calculate the cycle length and store them in table. If the table already contains the definition it returns the cycle length to main(). There I check if the returned cycle length is bigger then existing max cycle length.

Last thing set the first index of table to 1 since I haven’t used any condition to check if the number becomes 1. Also it is much faster than checking every time since the number is bound to converge in 1. So 1 is stored in look table when it is found its immediately returned.

table[1] = 1;

Rest i explained code comments. Hopefully it is easier to understand :).

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 10
100 200
201 210
900 1000

Output:

1 10 20
100 200 125
201 210 89
900 1000 174

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 100 ( 3n + 1 )
 */
#include<stdio.h>

#define SIZE 1000002

/* Lookup table for storing previously calculated values */
static unsigned table[SIZE];

/* Returns cycle length for given number */
unsigned cycleLength(register unsigned n){
    /* If the value already exists in the lookup table then return its cycle length */
    if (n < SIZE && table[n])
        return table[n];

    /* Check if number is odd */
    if (n&1){
        if (n < SIZE){
            /* Since 3n+1 becomes an even number, we perform the next step which is divided by two since its even, also +2 since we perform two operations */
            table[n] = 2 + cycleLength((3 * n + 1) >> 1);
            return table[n];
        }else
            /* The value is bigger than table so we calculate and return */
            return 2 + cycleLength((3 * n + 1) >> 1);
    }else{
        if (n < SIZE){
            /* The number is even so we perform number divided two, or bit shift left once */
            table[n] = 1 + cycleLength(n >> 1);
            return table[n];
        }else
            return 1 + cycleLength(n >> 1);
    }
}

int main(){
    unsigned a, b, count;
    register unsigned n;
    /* This is necessary since i don't check for 1 in cycleLength, Also 1st index is always 1 */
    table[1] = 1;

    while (scanf("%u%u", &a, &b) == 2){
        unsigned maxCycle = 0;
        /* The input may contain bigger number first then smaller number */
        if (a < b){
            for (n = a; n <= b; ++n){
                /* Cycle every value between a to b */
                count = cycleLength(n);
                /* We need to find max cycle, so if a cycle count is greater than maxCycle then replace maxCycle */
                if (maxCycle < count)
                    maxCycle = count;
            }
        }else{
            for (n = b; n <= a; ++n){
                count = cycleLength(n);
                if (maxCycle < count)
                    maxCycle = count;
            }
        }
        printf("%u %u %u\n", a, b, maxCycle);
    }
    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;
}