Distinct Partition Squares

+2 votes
asked Jul 26, 2018 by ravindra reddy (340 points)

Distinct Partition Squares

Problem Description

Among the several path breaking contributions to Number theory by the famous Indian mathematician Srinivasa Ramanujan, his contribution to partitions is extensive and deep. A partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be expressed as a sum of positive integers in the following ways: 1+1+1+1, 1+1+2, 1+3, 2+2, 4. Of these, only 1+3 and 4 use non repeating summands. Partitions using non repeating summands are called distinct partitions of n. There is no general formula for the number of partitions of an integer n and it is known that the partitions grow rapidly with n.

A k-distinct-partition of a number n is a set of k distinct positive integers that add up to n. For example, 3-distinct partitions of 10 are 1+2+7, 1+3+6,1+4+5 and 2+3+5

The objective is to count all k-distinct partitions of a number that have at least two perfect squares in the elements of the partition. Note that 1 is considered a perfect square.

Constraints

k<N<200, so that at least one k-distinct partition exists.

Input Format

The input consists of one line containing of N and k separated by a comma.

Output

One number denoting the number of k-distinct partitions of N that have at least two perfect squares in the elements of the partition.

Explanation

Example 1

Input

10, 3

Output

1

Explanation: The input asks for 3-distinct-partitions of 10. There are 4 of them (1+2+7, 1+3+6, 1+4+5 and 2+3+5). Of these, only 1 has at least two perfect squares in the partition (1+4+5).

Example 2

Input

12, 3

Output

2

Explanation

The input asks for 3-distinct partitions of 12. There are 7 of them (9+2+1, 8+3+1,7+4+1,7+3+2,6+5+1, 6+4+2, 5+4+3). Of these, two, (9+4+1, 7+4+1) have two perfect squares. Hence, the output is 2.

1 Answer

0 votes
answered Jul 26, 2018 by ravindra reddy (340 points)
#include <stdio.h>

int c=0,x;
int s[20];
int check(int n)
{
    int i,cn=0;
    for(i=1;i<=n;i++)
    {
        if(i*i == n)
            return 1;
    }
    return 0;
}
void sum(int k,int i,int m)
{
    int j,cn=0,f=0,l;
    if(k==0)
    {
        if(i<=m)
        {
            for(l=0;l<x-k-1;l++)
                if(s[l]==m)
                    f=1;
            if(f!=1)
            {
            s[x-k-1]=m;
            for(i=0;i<x;i++)
            {
                cn+=check(s[i]);
            }
            if(cn>=2)
                c++;
            }
        return;
        }
    }
    else
    {
        if(i>m)
            return ;
        for(j=i;j<m;j++)
        {
            for(l=0;l<x-k-1;l++)
                if(s[l]==j)
                    f=1;
            if(f==1)
            {
                f=0;
                continue;
            }
            s[x-k-1]=j;
            sum(k-1,j,m-j);
        }
    }
}
int main()
{
   int n,k,a[10],i,j;
   scanf("%d,%d",&n,&k);
   x=k;
   for(i=1;i<n;i++)
   {
        s[0]=i;
        sum(k-2,i,n-i);
   }
   printf("%d",c);
   return 0;
}
Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.
...