Black-white Board Game
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Both Fedya and Alex love playing games. One of their favorite games is playing with permutations. Description of game is given below.
Initially, they have a N x N matrix with all cells being white. Before starting the game, Alex colors the matrix in following way. he chooses N pair of integer L[i], R[i] denoting that in the i-th row, columns from L[i] to R[i] (1 - based indexing) are colored black.
The players play in rounds. In each round, both Alex and Fedor make a move. Alex moves first.
When a player makes a move, he needs to provide a permutation P of integer from 1 to N such that the number of inversions in this permutation is even for Alex (similarly odd for Fedya) and all the cells with the coordinates (i, Pi) in the matrix are black. It is prohibited to try already used permutations.
If during a round, both Alex and Fedya fail to find the required permutation, the game ends in a draw. If both Alex and Fedya find the required permutation, the game goes on to the next round. If one of the players fails to find the necessary permutation and the other guy finds a permutation, the game ends and the guy who managed to find the permutation wins.
The guys are intelligent enough to find the required permutation each time if it exists i.e. both players play optimally.
Now they're trying some big matrices, but they've became too lazy to play and now just want to know how will the game end on the given matrix. Can you please help them?
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the side of the matrix.
The following N lines will contain pairs of integers of the form Li Ri, denoting the range of the cells that are black in the corresponding row.
For each test case, output a single line containing the answer to the problem. Output "Draw" if the game ends with a draw, "Alex" if Alex wins and "Fedor" if Fedya wins.
1 ≤ Li ≤ Ri ≤ N
Subtask 1 (13 points)
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 7
Subtask 2 (26 points)
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 100
Subtask 3 (61 points)
- 1 ≤ T ≤ 15
- 1 ≤ N ≤ 105
Input: 1 2 1 2 1 1 Output: Fedor
In the first round, Fedya picks the permutation (2, 1) which has odd number of inversions (1) and the cells (1, 2) and (2, 1) are black. Alex is unable to pick the appropriate permutation, thus, he loses and Fedya wins. So we print "Fedor".
|Tags||april15, hard, heaps, matrices, merging, xcwgf666|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.