ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2009 > задача:


B. Knights of the Rook

Задачи сборника

• A. Tetris 3D
• B. Knights of the Rook
• C. Meat store
• D. Many-coloured roads
• E. Kovrov
• F. Interesting permutations
• G. What about judges?
• H. Triangles
• I. ATM

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Дмитрий Шевченко, ВлГУ.

Chess is a well known game, which also serves as a rich source of different math problems. Let us recall briefly characteristics of two chess pieces:
  • The rook can move from it's current position only in horizontal or vertical directions on any distance. Two rooks attack each other, if one is on the path of the other.
  • The knight moves the following way: first he moves 2 squares in horizontal or vertical direction and then 1 square in the perpendicular direction. In contrast to rooks, figures on the way of knight do not interfere with its movement. Two knights attack each other if they can move to each other's cells.
For centuries mathematicians have been solving problems like "Find the total number of ways one can put k rooks (or knights) on a chessboard so that no two of them are in the attacking positions". You will have to solve this problem too, but for a chess piece designed specially for you - the knightrook. This piece moves like the knight in northeastern direction and like the rook in southwestern direction. This chess piece is shown in figure 1. The initial location of knightrook is marked with a star. The cells that the knightrook can move to from initial location are marked with gray color. Two knightrooks attack each other if one is on the path of the other. Note that relation "attack" is not mutual here, in contrast to rooks and knights. If the knightrook attacks another one, the contrary is not true, but we still consider this an attacking position.

You must find the total number of ways one can put k knightrooks on an n x m chessboard so that no two of them are in the attacking positions. n is the number of chessboard rows (northern direction) and m is the number of chessboard columns (eastern direction).

Input
The first line contains three integers n, m and k separated by spaces (1 ≤ n ≤ 8, 1 ≤ m ≤ 17, 0 ≤ kn * m).
Output
Print a line containing the total number of ways one can put the given number of knightrooks on an n x m chessboard so that no two of them are in attacking positions.

Input 1 Output 1
2 2 1
4
Input 2 Output 2
2 2 3
0

Для отправки решений необходимо выполнить вход.

www.contester.ru