SGU 222 - Little Rooks

Description

Inspired by a “Little Bishops” problem, Petya now wants to solve problem for rooks.

A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move horizontally and vertically from its current position and two rooks attack each other if one is on the path of the other.

Given two numbers $n$ and $k$, your job is to determine the number of ways one can put $k$ rooks on an $n\times n$ chessboard so that no two of them are in attacking positions.

Input

The input file contains two integers $n$ ($1\leq n\leq 10$) and $k$ ($0\leq k\leq n^2$).

Output

Write index $I$ for given number as the first number in line. Write $I$ super-primes numbers that are items in optimal presentation for given number. Write these $I$ numbers in order of non-increasing.

Sample Input

 1  6 

Sample Output

 1 2  2 3 3 

Solution

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  #include #include using namespace std; const int MAX = 16; unsigned long long f[MAX]; int main() { f[0] = 1; for(int i = 1; i < MAX; i++) { f[i] = f[i - 1] * i; } int N, K; while(cin >> N >> K) { if(K > N) { cout << 0 << endl; } else { cout << f[N] / f[K] / f[N - K] * f[N] / f[N - K] << endl; } } return 0; }