Coin Distribution Problem

[passcode121]

Hi,

i am having a really hard time solving the following problem.
it looks really simple, but i cannot find a good implementation for it !!
if you have a good algorithm please tell me about it, thanks

The Problem:

Source File: coindst.c/ cpp/ pas/ java
Input: coindst.in
Output: coindst.out
We are interested in distributing a number of coins (each coin, say, is 1$) among a group of
people. For example, if there are two coins and two persons there are 3 ways to distribute the two
coins:
· The first person gets the two coins and the other person gets nothing.
· The first person gets one coin and the other also gets one coin.
· The first person gets nothing and the other person gets the two coins.
In general, we want to find all ways to distribute n coins among k people. Each person may get from
0 coin to n (all) coins. Write a program that reads a sequence of pairs of integers from an input file,
each pair specifying a value for n and a value for k, and writes to the output file all different ways
to distribute the n coins among the k people. The program terminates if the number of people k = 0.
Input file:
The input file is named coindst.in and contains lines each of which contains a pair of non-negative
integer values n and k. The end of data is indicated by a row with the number of persons k =0. The
maximum value for k is 10.
Output file:
The output file is named coindst.out. Each line consists of one way to distribute the n coins among the
k persons. Output lines corresponding to different pairs of n and k are separated by a blank line.
Sample input:
4 2
3 3
5 0
Sample output:
4 0
3 1
2 2
1 3
0 4

3 0 0
2 1 0
2 0 1
1 2 0
1 1 1
1 0 2
0 3 0
0 2 1
0 1 2
0 0 3

[Derek Elensar]

Someone correct me if I'm wrong, but you would need to use a series of for loops, correct?
Consider the following program:

#include <iostream>
#include <cstdlib>
using std::cout;

int main()
{
    int i,j,k,l,m;

    cout << "i j k l m\n";
    for (i = 0; i <= 1; i++)
        for (j = 0; j <= 1; j++)
            for (k = 0; k <= 1; k++)
                for (l = 0; l <= 1; l++)
                    for(m = 0; m <= 1; m++)
                        {cout << i << ' ' << j << ' ' << k << ' ' << l << ' ' << m << '\n';}
    system("pause");
    return 0;
}

It lists all of the binary values for the numbers 0-31. You can do a similar program that uses for loops to list all of the possible outcomes like the ones you listed in this fashion:

Sample input:
4 2
3 3
5 0
Sample output:
4 0
3 1
2 2
1 3
0 4

3 0 0
2 1 0
2 0 1
1 2 0
1 1 1
1 0 2
0 3 0
0 2 1
0 1 2
0 0 3

This should be able to get you some headway.

[mike_2000_17]

>>i cannot find a good implementation for it !!

That's a good thing! The point of a homework problem is not for you to go out and google for a ready made algorithm. Nor is it for you to come to a forum like this one, paste the assignment problem, and wait for someone to post a full piece of working code.

The point is that you should think about it, try to solve it, make the code work. If you show that you have tried your best at coming up with some working code by yourself, then you can ask for hints on this forum. Don't expect complete code after demonstrating no efforts, that won't benefit you and that's why we wouldn't post that.

[passcode121]

>>i cannot find a good implementation for it !!

That's a good thing! The point of a homework problem is not for you to go out and google for a ready made algorithm. Nor is it for you to come to a forum like this one, paste the assignment problem, and wait for someone to post a full piece of working code.

The point is that you should think about it, try to solve it, make the code work. If you show that you have tried your best at coming up with some working code by yourself, then you can ask for hints on this forum. Don't expect complete code after demonstrating no efforts, that won't benefit you and that's why we wouldn't post that.

thanks, you are right except for one thing, its not a homework problem
i spent 2 days trying to solve it but i couldn't come up with a solution.

>>i cannot find a good implementation for it !!

my English is not that good, i used the wrong word XD.

thanks Derek Elensar, that's the way i was trying to implement it with

the code i was working on is:

#include <iostream>
#include <fstream>
using namespace std;

void Emptyarray(int a[],int size);
void printarray(int a[],int size);
void printarray(int a[],int size,ofstream &out );
void moveo(int a[],int from,int to);
void moven(int a[],int from,int to,int i);
void Resetarray(int a[],int size,int n);
int main()
{
    ifstream in("coindst.in");
    ofstream out("coindst.out");
    if(!in) { cout<<"Input File Not Found"; return(1);}
    int n,k,a[10]={0};


    while(in>>n)
    {
        in>>k;
        if(k==0)
        {
            return 0;
        }
        k--;
        a[k]=n;

printarray(a,k);

        for (int i=k; i >= 0; i--)
        {
            for(int j=1; j<n; j++)
            {
                for(int c=1; c<=i; c++)
                {
                    a[i]=a[i]-j;
                    a[i-c]=a[i-c]+j;
                    for(int m=i-1; m>=0; m--)
                    {
                        a[m]--;
                        a[m-1]++;
                        printarray(a,k);
                    }
                    Resetarray(a,k,n);
                }
            }
        }

    }






    return 0;
}


void printarray(int a[],int size, ofstream &out)
{

    for(int i=size; i>=0 ; i--)
    {
        out<<a[i]<<" ";
    }
    out<<endl;
}

void printarray(int a[],int size)
{

    for(int i=size; i>=0 ; i--)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;

}

void Emptyarray(int a[],int size)
{

    for(int i=size; i>=0 ; i--)
    {
        a[i]=0;
    }

}

void moveo(int a[],int from,int to)
{
    a[from]--;
    a[to]++;
}


void moven(int a[],int from,int to,int i)
{
    a[from]=a[from]-i;
    a[to]=a[to]+i;
}

void Resetarray(int a[],int size,int n)
{
    Emptyarray(a,size);
    a[size]=n;
}

[passcode121]

finally, i solved it using recursion :)

thanks

code:

#include <iostream>
#include <fstream>
using namespace std;
void dist(int a[],int size,int base);
void Emptyarray(int a[],int size);
void printarray(int a[],int size,ofstream &out );
void Resetarray(int a[],int size,int n);
void dist(int a[],int size,int base,ofstream &out);
void copyarray(int a[],int s[],int size);

int main()
{
    ifstream in("coindst.in");
    if(!in)
    {
        cout<<"Input File [coindst.in] Not Found"<<endl;
        in.close();
        return 1;
    }

    ofstream out("coindst.out");

    int n,k,a[10]={0};
    while(in>>n)
    {
        in>>k;
        Resetarray(a,k,n);
        if(k==0)
        {
            return 0;
        }
        dist(a,k-1,k-1,out);
        out<<endl;
    }

    return 0;

}

void printarray(int a[],int size, ofstream &out)
{

    for(int i=size; i>=0 ; i--)
    {
        out<<a[i]<<" ";
    }
    out<<endl;
}

void Emptyarray(int a[],int size)
{
    for(int i=size; i>=0 ; i--)
    {
        a[i]=0;
    }
}

void Resetarray(int a[],int size,int n)
{
    Emptyarray(a,size);
    a[size-1]=n;
}
void dist(int a[],int size,int base, ofstream &out)
{
    printarray(a,size,out);
    if(base==0)
    {
        return;
    }
    int s[10]={0};
    while(a[base]>0)
    {
        a[base]--;
        a[base-1]++;
        copyarray(a,s,size);
        dist(a,size,base-1,out);
        copyarray(s,a,size);
    }
}

void copyarray(int a[],int s[],int size)
{
    for(int i=0;i<size;i++)
    s[i]=a[i];
}