SPOJ Problem DCEPC504

The Indian Connection

Explanation:

In this problem, we use recursion to find the result of a query given by (n, k) where n is the generation no. and k is the kth child in nth generation.

Initially, n and k are 1-based, we make them 0-based first. Now, the base condition in our recursion becomes:

if n is 0: return 'm' (m stands for male and f for female),
which is for the first level and is pretty clear.

Now, if the above condition doesn't match, we try to find out the gender of parent of current k which is given by (int)k/2, and in the current level, if k is first child of the parent, child will be same as parent else opposite.

Here is the code presented for the above problem.

Solution:

#include<cstdio>

typedef long long int LLD;

char recurse(int y, LLD i){
    //  base condition
    if(y == 0 && i == 0)
    return 'm';

    //  find index of parent which is i/2
    LLD par = i >> 1;

    //  find the gender for parent using recursion
    char c = recurse(y - 1, par);

    //  if child is first child of parent
    if(i == 2 * par)
        c = ((c == 'm') ? 'm' : 'f');

    //  if child is second child of parent
    else
        c = ((c == 'm') ? 'f' : 'm');
    return c;
}

int main(){
 
    int y, t;
    LLD idx;
    scanf("%d", &t);
    while(t--){
        scanf("%d%lld", &y, &idx);

        //  make y and idx zero-indexed
        y--;
        idx--;

        //  call recurse on y and idx to find the result
        printf("%s\n", ((recurse(y, idx) == 'm') ? "Male" : "Female"));
    }
    return 0;
}

Problem COLONY can also be solved using the same strategy.

Any suggestions are welcome.