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

There’re bacterias in the Petri dish. The only thing they can do is to reproduce themselves everyday.

After one bacteria reproduce itself, there will be one origin bacteria and y newborn bacterias.
Suppose there’re x bacterias on the first day.
Your task is to compute how many bacterias on the n-th day.

Please output the answer modulo 10177 because the answer may be too large to be represented by int.

Hint: if you got TLE, try to optimize power by recursion.

#define MOD 10177
// Ch7 Slide P.35
// compute an
int fast_pow(int a, int n){
    if( n == 0 ){ // basis
        return 1;
    }
    else{ // resursive 
        int k = ???;
        // if n is even:
        // return (k*k)%MOD
        // if n is odd:
        // return ???
    }
}

Input

There are multiple lines of input.
Each line contains 3 positive integers x,y,n

• 0 ≤ x, y ≤ 10,000
• 1 ≤ n ≤ 10,000,000
• The input is ended by EOF.

Output

Print the number of bacterias on the n-th day modulo 10177 for each line of input.
Remember ‘\n’ on the end of line.

Explantation of Sample I/O:

• (1, 0, 9): 1 bacteria at first day. There’re no newborn bacteria after reproduction. There’s still 1 bacteria on 9-th day.
• (4, 5, 6): 4 bacterias at first day. After every bacteria reproduce itself, there’re 4 + 4*5 bacterias on the second day. On 6-th day, there’re 31,104 bacterias, 31104 modulo 10177 = 573

Sample Input  Download

Sample Output  Download

Tags

Discuss