Find The Ring (PUZZLE)

There is a new magician in town. His trick is known as "Find the Ring". He puts 3 glasses at 3 spots on the table, labeling them as 0, 1 and 2. Now, he hides a ring under one of the glasses. The glasses are opaque and placed upside down, so that the ring is not visible to the audience. Now, he begins to make certain swaps in between adjacent glasses, i.e. the glass at position 0 can be swapped with that at position 1, and the glass at position 2 can be swapped with glass at 1. Assuming that all swaps are done randomly with equal probability of 50%, you have to find index of the glass that is most likely to have the ring, at the end. In case of a tie, choose the one with lower index. Assume that the glass containing the ring was swapped exactly N times. Input: First line contain two space separated integers, index and N. index is index of glass that initially contains the ring and N is the total number of swaps involving the glass with ring.

SAMPLE INPUT 
3 
1 1
0 1
2 2
SAMPLE OUTPUT 
0 
1 
0

Explanation 
Case 1: The ring is at index 1. There is only one swap to be made. The probability of ring ending up at 0 is .5, at 1 is 0 and at 2 is also .5 So, we have a tie between positions 0 and 2. We must choose the lower index, i.e. 0
Case 2: The ring is at index 0. There is only one swap to be made. There is also only one choice. The probability of ring ending up at 0 is 0, at 1 is 1 and at 2 is 0. The maximum probability occurs at index 1.
Case 3: The ring is situated at index 2. There are 2 swaps to be made. So, we can make following swaps: {2 -> 1 -> 0} or {2 -> 1 -> 2} Hence, the probability of ring ending up at 0 is .5, at 1 is 0 and at 2 is .5 Again, there is a tie between 0 and 2, and we choose 0, i.e. the lower index.

CODE

Comments

Post a Comment

Popular posts from this blog

Female co passenger hack

The female co-passenger hack. I came across this trick on the internet. When you need to book a ticket on IRCTC (Indian Railways), book two seats instea of one, and cancel one after some days. One in your name and one in fake Female name to get a girls in the compartment. The IRCTC algorithm works that way.
Read more

C library function - qsort()

Image
Description               The C library function void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) sorts an array. Parameters base -- This is the pointer to the first element of the array to be sorted. nitems -- This is the number of elements in the array pointed by base. size -- This is the size in bytes of each element in the array. compar -- This is the function that compares two elements. Return Value This function does not return any value Code   #include <stdio.h> #include <stdlib.h> int values [] = { 88 , 56 , 100 , 2 , 25 }; int cmpfunc ( const void * a , const void * b ) { return ( *( int *) a - *( int *) b ); } int main () { int n ; printf ( "Before sorting the list is: \n" ); for ( n = 0 ; n < 5 ; n ++ ) { printf ( "%d " , values [ n ]); } qsort (...
Read more

Wildcard Pattern Matching (DP)

Given a text and a wildcard pattern, implement wildcard pattern matching algorithm that finds if wildcard pattern is matched with text. The matching should cover the entire text (not partial text). The wildcard pattern can include the characters ‘?’ and ‘*’ ‘?’ – matches any single character ‘*’ – Matches any sequence of characters (including the empty sequence) Text = "baaabab", Pattern = “*****ba*****ab", output : true Pattern = "baaa?ab", output : true Pattern = "ba*a?", output : true Pattern = "a*ab", output : false Each occurrence of ‘?’ character in wildcard pattern can be replaced with any other character and each occurrence of ‘*’ with a sequence of characters such that the wildcard pattern becomes identical to the input string after replacement. Let’s consider any character in the pattern. Case 1: The character is ‘*’ Here two cases arise We can ignore ‘*’ character and move to next character in the Pattern. ‘*’ cha...
Read more