Squares GameProblem code: SQUAGAME |
All submissions for this problem are available.
Fat Tony and Fit Tony are playing the square painting game. There are n squares drawn on a plane. The sides of the squares are parallel to the axes. Squares don't intersect, but some of them can be inside others. In his turn a player can choose any square and paint it's internal area black. All squares inside the painted one are also painted black. The player can't paint the squares that were already painted. The loser is the player who can't make a turn. Determine the winner of the game if both players play optimally and Fat Tony's turn is the first. Also if Fat Tony can win the game determine which square he has to paint on his first turn in order to win. If there are many squares which guarantee victory to Fat Tony choose the one with the smallest number.
Input
The first line of input contains t - the number of test cases. Each test case starts with n - the number of squares. Next n lines consist of three integers each x, y, a - the coordinates of the lowest left corner of the sqaure and the length of it's sides. The squares in the input are numbered from 1 to n in the order they are listed.
Constraints
1 <= t <= 10
1 <= n <= 50000
The total number of squares over all test cases in one file won't exceed 250000.
x, y won't exceed 108 in absolute value.
a will be positive and less than 108.
Output
For each test case print "Fat x", where x - is the number of square which needs to be painted on the first turn in order to win (if there are many such square chose the one with the smallest number), if Fat Tony wins or "Fit" if Fit Tony wins.
Example
Input: 2 5 0 0 10 15 15 1 1 1 3 5 5 1 14 14 3 2 1 1 1 3 3 1 Output: Fat 2 Fit
| Author: | spooky |
| Date Added: | 26-12-2010 |
| Time Limit: | 5 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Can I paint a square if it is
Can I paint a square if it is partially painted ?
Also, can two sqares touch
Also, can two sqares touch each other?
Is the output for the tc 1 is
Is the output for the tc 1 is correct...?
@utkarsh lath You can paint
@utkarsh lath
You can paint the partially painted square. Squares won't touch.
Accepted with C++ 4.0.0-8 and
Accepted with C++ 4.0.0-8 and got Runtime Error with C++ 4.3.2 with exactly same code...
Considering the first test
@Ziaul: Look again carefully
@Ziaul: Look again carefully :)
@Ziaul::it's cordinate of
@Ziaul::it's cordinate of left,top of square
@Ivan Mistreanu - 1st
@Codechef team, It seems you
@Codechef team, It seems you people don't try to improve the Site.
"Oops, We are Sorry to load the recent activity" is a constant business.
I guess you might have not noticed this, since you might be having blazing fast Internet, but most of the Indian Students don,t have.
Try Improving this, give a ranking page instead like that in cook-off, that is better than this Ajax .
What is importance of ajax, if gives 90% of the times : ------> " Ooops" .
Plz improve this thing as soon as possible.
How Can you guys be so lazy, cmon wake up.
@Yamazoe , I think that won't
@Yamazoe , I think that won't affect your answer , if you got the correct algorithm.
i.e. Assume 2nd square will get painted as soon as you paint the first one.