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.

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

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 1st element with the 1st element, the 2nd element, the 3rd element, and the 4thelement, 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.

You will be provided with the following sample code, and asked to implement function "Swap" and "Perm.

#include <stdio.h>

char list[10];

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*/
}

int main(void)
{
    int num, i;

    scanf("%d", &num);

    for(i=0; i<num; i++)
        list[i] = '1'+i;
    Perm(0, num);

    return 0;
}

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

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

Infix notation: X + Y

• Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."

Prefix notation (also known as "Polish notation"): + X Y

• Operators are written before their operands. The expressions given above are equivalent to / * A + B C D

Now, please write a program to convert the given expressions from prefix to infix.

Input

The first line contains a positive integer N, indicating the number of testcases in this input.

In the following N lines, each line contains a prefix expression.

In each prefix expression, there is a space between numbers and operators, and operators and operators.

Output

Output the infix expression and its answer of each given prefix expression.

Note that

• There is a space between numbers and operators, and operators and operators.
• If the answer is integer, there is no need to print decimal point. Otherwise, you should print only one digit after the decimal point.
• You have to print a '\n' at the end of each ouput.
• Add a pair of parentheses to wrap around each operator and its operands.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Writer : jjjjj19980806

Description : pclightyear

jjjjj doesn't like long description.

Given integers a, n, p, please calculate the value of aⁿ mod p.

Input

The first line contains an integer T, representing the number of testcases.

Each testcase contains a line with three integer a, n, m.

It is guaranteed that :

• 1 ≤ T ≤ 1000
• 1 ≤ a, n, p ≤ 10⁹

Output

For each testcase, please output a line contains one integer representing your answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Calculate the greatest common divisor of multiple positive integers.

Definition of greatest common divisor: if d is a common divisor of a set of positive integer S, then for all element i in S, d|i. The greatest common divisor is the largest d satisfy the above condition.

Input

Input consists of 2 lines.

The first line contains a integer N, representing the # of positive integers.

The second line contains N positive integers. Numbers are seperated by a space.

It is guaranteed that

• N <= 10000
• All positive integers <= 2*10¹²

Output

Print out the greatest common divisor of these positive integers.

Sample Input  Download

Sample Output  Download

Tags

Discuss