Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Queens in peaceful positions
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1306Accepted: 584


On a chessboard of size NxN (N<=50) N queens are placed. We'll say that queens are in peaceful position if none of them can attack another. You are to find the total amount of peaceful positions that can be obtained from the given peaceful position by rearranging of exactly three queens.


The first line of input will contain an integer number N that represents the size of a chessboard (and the number of queens also). It will be followed by N lines describing positions of queens. Each line will contain two integers X and Y separated by a space. These numbers represent horizontal and vertical coordinates and lay in a range from 1 to N.


The output consists of a single integer representing the number of peaceful positions that can be achieved from initial position by moving of exactly three queens. Note: queens are not numbered so if you rearrange them on the chessboard using only squares they already occupied you'll always get the same peaceful position, not the new one.

Sample Input

2 1
1 3
3 4
4 2

Sample Output



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator