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