Description

Suppose that you have an infinite number of containers with different sizes, already filled with water. Given another empty container with size N liters, you need to find out all the possible methods to fill this N-liter empty container using the provided smaller containers. Note that, to avoid water wastage, if you choose to use a container, all the water in this container should be poured.

For example, assume that we have containers in 1, 5, and 10 liters. To get the 17 liters of water, all the possible methods are listed below:

1. 1 container of 10 liters, 1 container of 5 liters, and 2 containers of 1 liter.
2. 1 container of 10 liters, 0 containers of 5 liters, and 7 containers of 1 liter.
3. 0 containers of 10 liters, 3 containers of 5 liters, and 2 containers of 1 liter.
4. 0 containers of 10 liters, 2 containers of 5 liters, and 7 containers of 1 liter.
5. 0 containers of 10 liters, 1 container of 5 liters, and 12 containers of 1 liter.
6. 0 containers of 10 liters, 0 containers of 5 liters, and 17 containers of 1 liter.

Note that

1.      This problem involves three files.

• function.h: Function definition of filliing and showResult.
• function.c: Function describe of filling and showResult.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.cpp.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose C compiler) 

       Step 2. Check the results and debug your program if necessary.

function.h

main.c

 Hint 

You can use the following incomplete code of function.c to solve this problem.

function.c

Input

The input contains three lines.

The first line contains an integer M (0<M<=5) which represents the number of different size containers.

The second line contains M numbers, S1 ,S2 , …, SM. Si represents the size of the i-th container. Note that these M numbers are in decreasing order.

The third line contains an integer N (0<M<100) which represents the size of the empty container.

Output

Display all the possible methods to fill the empty container. Each line represents a method in the format “(C1,C2,…,CM)”, where Ci represents the number of the size Si container.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10832.c

Partial Judge Header

10832.h

Tags

Discuss

Description

Given a set of n≧1 elements, the problem is to print all possible permutations of this set. For example, if the set is (1,2,3), then the set of permutations is {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,2,1), (3,1,2)}.

 

<Hint1>

Looking at the case of four elements (1,2,3,4). The answer can be constructed by writing

1. ‘1’ followed by all the permutations of (2,3,4)
2. ‘2’ followed by all the permutations of (1,3,4)
3. ‘3’ followed by all the permutations of (1,2,4)
4. ‘4’ followed by all the permutations of (1,2,3)

 

<Hint2>

A recursive method to implement the above idea is as follows:

Consider the case of (1,2,3,4), that is, n=4.

1. Place the set elements in a global array, and set the position index “k” as 0.
2. Use a for-loop to “swap” (or exchange) the 1^st element with the 1^st element, the 2^nd element, the 3^rd element, and the 4^th element, respectively.
   • In each loop-iteration:
     1. increment the position index “k” by 1 (for considering only the remaining elements in the following recursive call);
     2. use the updated k to recursively call your permutation function;
     3. note that because you use a global array, remember to swap back the two elements after the iteration.
3. In a recursive-call path, when k reaches n, it means that you get a possible permutation.

 

Note that

1.      This problem involves three files.

• function.h: Function definition of show, Swap and Perm.
• function.c: Function describe of show, Swap and Perm.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.c.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

function.h

#ifndef FUNCTION_H #define FUNCTION_H void show(int n); void Swap(int k, int i); void Perm(int k, int n); char list[10]; #endif

main.c

#include <stdio.h> #include "function.h" int main(void) { int num, i; scanf("%d",&num); for(i=0; i<num; i++) list[i]='1'+i; Perm(0,num); return 0; }

function.c

#include <stdio.h> ​#include "function.h" void show(int n) { int i; printf("(%c", list[0]); for (i=1; i<n; i++) { printf(",%c", list[i]); } printf(")\n"); } void Swap(int k, int i) { /*your code*/ } void Perm(int k, int n) { /*your code*/ }

Input

The decimal number n that represents the number of elements in the set.

(1≦n≦5)

Output

In the output you should print all the permutations.

Be sure to add a newline character '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10833.c

Partial Judge Header

10833.h

Tags

Discuss