The Indian Connection SPOJ

SPOJ Problem Set (classical)

11402. The Indian Connection

Problem code: DCEPC504

Rajesh Kuthrapali has a weird family structure. Every male member gives birth to a male child first and then a female child whereas every female member gives birth to a female child first and then to a male child. Rajesh analyses this pattern and wants to know what will be the Kth child in his Nth generation. Help him.

Note:

1.Every member has exactly 2 children.

2. The generation starts with a male member(Rajesh).

3. In the figure given below:

                                   M-------- 1st generation 

                              /        \
                          M             F ------- 2nd generation
                        /    \         /   \
                      M     F       F     M
                                      |
                                   3rd child of 3rd generation

Input

First line specifies T, the number of test cases.

Next T lines each gives 2 numbers, N and K

Output

Output 1 line for each test case giving the gender of the Kth child in in Nth generation.

Print “Male” for male “Female” for female (quotes only for clarification).

Constraints

1<=T<=100

1<=N<=10000

1<=K<=min(10^15 , 2^(n-1))

Example

Input:
4
1 1
2 1
2 2
4 5 
Output:
Male
Male
Female
Female

solution---


this question is related to THUE MORSE series.
sequence http://oeis.org/A010060

how to create THUE MORSE series--

a(2n)=a(n)
a(2n+1)=1-a(n)

let for n=0,a(0)=0;

n = 0, substituting in Eq. 1: t1 = 1 - t0 = 1 (t0 is 0)

n = 1, substituting in Eq. 2: t2 = t1 = 1

n = 1, substituting in Eq. 1: t3 = 1 - t2 = 1 - 1 = 0

n = 2, substituting in Eq. 2: t4 = t2 = 1

n = 2, substituting in Eq. 1: t5 = 1 - t4 = 1 - 1 = 0

n = 3, substituting in Eq. 2: t6 = t3 = 0

n = 3, substituting in Eq. 1: t7 = 1 - t6 = 1 - 0 = 1

HERE is the code

#include
int main()
{
    int t,count;
    long long int k,num;
    scanf("%d",&t);
    while(t--)
    {
        count=0;
        scanf("%lld %lld",&k,&num);
        if(num==1)
            printf("Male\n");
        else if(num==2)
            printf("Female\n");
        else{
            num=num-1;
        while(num>1)
        {
            if(num%2!=0)
                count+=1;
            num=num/2;
        }
        if(count%2==0)
            printf("Female\n");
        else
            printf("Male\n");
        }
        printf("\n");
    }
    return 0;
}