Geek Sundaram attains inner peace
All submissions for this problem are available.
To attain inner peace Geek Sundaram has to pass through the "Hall of Valley of Death". The floor of this hall is a square with length 100 m. It is laid with square tiles of size 1 X 1 arranged over the entire hall. But, at some places in the hall tiles are broken. The moment a person enters the hall, the underworld awakens and dead souls emerge from these broken tiles. The only way to escape from these evil souls is to completely cover the broken locations with magic planks from the room of requirements. Each plank has size 100 X 1 and can only be placed parallel to either sides of the floor. Now Geek Sundaram has to save himself from these evil souls. He figures out that he has to use the minimum number of planks possible. Please help Geek Sundaram to attain inner peace.
- The first line of the input is a positive integer t <= 30, denoting the number of halls.
- The descriptions for the t halls follow one after the other.
- Hall Description:
- The first line of the hall description is a positive integer n (n <= 10000), denoting the number of broken tile locations.
- This is followed by the n lines, one for each broken tile location.
- Each line contains two integers x y (0 <= x, y < 100), separated by a single space, representing the co-ordinates of the broken tile location.
The output should consist of t lines, one for each hall. The kth line in the output should be an integer mk, the minimum number of planks needed for the kth hall.
4 4 Output:
|Time Limit:||1 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