Question

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.

Answer 1

#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;
}