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.

SPOJ Problem AE00

Rectangles

Explanation:

The problem asks us to print the no. of rectangles(remember squares are also rectangles) that can be generated from 'n' squares each of length 1.

First, we try to see how many squares can be generated using n squares:

• n = 1, only one square of 1x1 is possible.
• n = 2, only one square of 1x1 is possible.
• n = 3, only one square of 1x1 is possible.
• n = 4, two squares are possible of size 1x1 and 2x2.
• n = 5, two squares are possible of size 1x1 and 2x2.
• n = 6, two squares are possible of size 1x1 and 2x2.
• ...........
• n = 8, two squares are possible of size 1x1 and 2x2.
• n = 9, three squares are possible of size 1x1, 2x2 and 3x3.
• n = 10, three squares are possible of size 1x1, 2x2 and 3x3.
• ...........
• n = 15, three squares are possible of size 1x1, 2x2 and 3x3.
• n = 16, four squares are possible of size 1x1, 2x2, 3x3 and 4x4.
• and so on.

Looking at the above values, we can easily say that no. of squares will be equal to floor(sqrt(n)).

Now, we see how many rectangles we can get for given 'n'.
We take:

• n = 1:
• for this value of 'n', we cannot have any rectangle possible.
• n = 2: 
• here, we can have 2 rectangles of size 1x2 and 2x1 but, since 1 rectangle can be rotated and moved to produce another rectangle, we consider only 1 rectangle.
• n = 3:
• here, we can have 4 rectangles of size 1x2, 2x1, 1x3, 3x1; but since 1x2 or 2x1 rectangle can be rotated or moved to obtain other rectangle and similar is the case for 1x3 and 3x1.
• n = 4:
• here, we can have 6 rectangles of size 1x2, 2x1, 1x3, 3x1, 1x4, 4x1. Again, we have 3 pairs, which can be generated from one another, namely, (1x2, 2x1), (1x3, 3x1) and (1x4, 4x1). Thus, we can have a total of 3 rectangles.
• n = 5:
• here, we can have 8 rectangles of size 1x2, 2x1, 1x3, 3x1, 1x4, 4x1, 1x5, 5x1. As described in above condition, we have one extra pair (1x5, 5x1), which can be generated from one another. Thus, we have a total of 4 rectangles.
• n = 6:
• here, we can have 12 rectangles of size 1x2, 2x1, 1x3, 3x1, 1x4, 4x1, 1x5, 5x1, 1x6, 6x1, 2x3, 3x2. Here, apart from above pairs, we have 2 more pairs, which are (1x6, 6x1), (2x3, 3x2). Thus, in total, we have 6 rectangles.

Considering above rectangles, we can say that we only count those rectangles of form (ixj) where i < j, i * j <= n and value of i is atmax equal to floor(sqrt(n)).

Finally, adding both the number of squares and rectangles, we can have the desired output.

Here is the code presented for the above problem.

Solution:

#include<cstdio>
#include<cmath>

int main()
{
    int i,j,n,cnt=0;
    scanf("%d",&n);

    //    counting no. of rectangles
    for(i=1;i<=sqrt(n);i++)
        for(j=i+1;i*j<=n;j++)
            cnt++;

    //    counting no. of squares
    cnt+=sqrt(n);
    printf("%d",cnt);
    return 0;
}

Any suggestions are welcome.

SPOJ Problem TEST

Life, the Universe, and Everything

Explanation:

The problem is self-explanatory. Run an infinite loop, read the numbers and keep on printing them until you get a 42.

Solution (C++):

#include<cstdio>

int main(){
    int n;
    while(1){
        scanf("%d", &n);
        if(n==42)
            break;
        printf("%d\n", n);
    }
    return 0;
}

Any suggestions are welcome.