Help in a problem asked in Infosys Coding contest (Teaser Round)....

general
,
1

A little help/hint would be appreciated. Also, the teaser round had ended at 7 PM if you are wondering that I’m cheating or not. :stuck_out_tongue:

Input : Standard Input
Output : Standard Output

Time Limit : 1 sec

It is an interesting problem to count the number of unordered partitions of a number N. This is generally done by putting N non-negative numbers in non-increasing order along a 1xN board, which sum to N.

In this problem however, you are given a 2xN board. You need to fill in non-negative numbers in this board in such a way, that
(1) The sum of all the numbers filled = N

(2) Each of the 2 rows consist of numbers in non-increasing order

(3) Each of the N columns consist of numbers in non-increasing order.

In how many ways can this be done, given the number N? Two ways are considered different if there is a cell in the board which has different numbers.

Input:

The first line consists of the number of testcases T. Each testcase consists of a single integer N.

Output:

For each testcase, output a single line, giving the number of ways.

Constraints:

T <= 10
N <= 70

The answer will fit in a 64 bit signed integer .

Sample Input:

1 5

Sample Output:

16

2

This Problem reduces to a very simple formula for every integer n…

f(n) = 1+2+4+6+.... upto (n-1) terms + C
where C=n/2 for every integer...

for eg for n=5 as in ur test case…
f(5)=1+2+4+6+C(=5/2 + 1) ; f(5) = 16
check for some smaller values like n=4 or 3 and start filling the table following the rules, you ll quickly understand how i came up with this formula thing… :slight_smile:

4 Likes
3

It is an interesting problem to count the number of unordered partitions of a number N. This is generally done by putting N non-negative numbers in non-increasing order along a 1xN board, which sum to N.

In this problem however, you are given a 2xN board. You need to fill in non-negative numbers in this board in such a way, that
(1) The sum of all the numbers filled = N
(2) Each of the 2 rows consist of numbers in non-increasing order
(3) Each of the N columns consist of numbers in non-increasing order.

In how many ways can this be done, given the number N? Two ways are considered different if there is a cell in the board which has different numbers.
Input:

The first line consists of the number of testcases T. Each testcase consists of a single integer N.
Output:

For each testcase, output a single line, giving the number of ways.
Constraints:
T <= 10
N <= 70
The answer will fit in a 64 bit signed integer.
Sample Input:

1
5

Sample Output:
16
PLEASE UPLOAD THE CORRECT ANSWER FOR THE ABOVE QUESTION

4

Here is a program that solves the problem :

int main ()
{
    float a,i,b,sum=1,c;
    scanf("%f", &a);
    scanf("%f", &b);
    for(i=0;i<a;i++)
    {
       for(i=0;i<=b;i++)
       {
           sum+=2;
       }
    }
    c=b/2;
    printf("%.0f",ceil(sum+c));
 


}
2 Likes
5
4 Likes
6
3 Likes