| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11212 | Fill water |
|
| 11222 | N queens |
|
| 11710 | GCD(recursive) |
|
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 container of 10 liters, 1 container of 5 liters, and 2 containers of 1 liter.
- 1 container of 10 liters, 0 containers of 5 liters, and 7 containers of 1 liter.
- 0 containers of 10 liters, 3 containers of 5 liters, and 2 containers of 1 liter.
- 0 containers of 10 liters, 2 containers of 5 liters, and 7 containers of 1 liter.
- 0 containers of 10 liters, 1 container of 5 liters, and 12 containers of 1 liter.
- 0 containers of 10 liters, 0 containers of 5 liters, and 17 containers of 1 liter.
You will be provided with the following sample code, and asked to implement function "filling".
#include <stdio.h>
#define MAXNC 5
int liters[MAXNC];
int solution[MAXNC];
void showResult(int n) {
int i;
printf("(%d", solution[0]);
for (i=1; i<n ;i++) {
printf(",%d", solution[i]);
}
printf(")\n");
return;
}
void filling(int amount, int cur, int n) {
/*Your code*/
}
int main(void) {
int n, i;
int water;
scanf("%d", &n);
for (i=0; i<n ;i++) {
scanf("%d", &liters[i]);
}
scanf("%d", &water);
filling(water, 0, n);
return 0;
}
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 Cirepresents the number of the size Si container.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You have to place N queens on a NxN chessboard in such a way that no queen threatens another one
The rule is that each row and column of the board contains exactly 1 queen , and each diagonal contains no more than 1 queen.
Your mission is to compute how many possible ways to place N queens on that chessboard.
Input
An integer N which represent the size of chessboard and the number of queens.
where 1<=N<=10
Output
An integer which represent the number of possible distributions of N queens.
There is no need to add '\n' at the end of output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two positive integers a and b, compute the greatest common divisor (GCD) of a and b. The GCD of a and b is the biggest integer that can divide a and b with no reminder.
Input
First line contains a positive integer t (t<=10000), which indicates the number of test cases in the input. In the next t lines, each line contains two positive integers a, b, which are smaller than or equal to 10^6.
Output
For each case, output the GCD of a and b in a line.