AppleTreesProblem code: DPC201 |
All submissions for this problem are available.
Apple Trees
Apple trees in a garden form a rectangular grid. A group of monkeys lives on these
trees. Not more than one monkey lives in each tree. A monkey feels happy to believe that it is
the lord of all apple trees it views from the top of the tree it lives in. However, as the trees are
of different heights a monkey can view trees that are not obstructed from its view by other
trees. A monkey that views the maximum number T of trees is a lord of lords. The undisputed
monarch is the lord of lords that lives in the highest tree. In case two or more lord of lords
have the claim to be the monarch then monarchy is disputed.
Assume that the ground of the garden is plane; vertical straight lines represent trees;
trees are at a distance of unity row-wise or column-wise; and the height of each tree is an
integer in the unit of the distance. A tree of height zero in a position indicates absence of a
tree on that position. Visibility of a tree R from the top of a tree P depends on heights and
locations of P, R and other trees. A tree R is invisible from the top of a tree P if and only if
there exists a visible tree Q that lies on the vertical plane containing P and R and is located
between P and R so that the top of R is either on or below, the line joining tops of P and Q.
Write a program to locate the undisputed monarch, given heights of all trees.
Input
The input may contain multiple test cases.
For each test case, the first line gives two integers m and n representing respectively
the total number of rows and columns of trees in the garden. Each of the next m lines
contains n integers representing heights of trees in a row. The jth integer in the ith row
represents the height of the tree in ith row and jth column of the garden. Assume that the
garden contains no more than 200 trees.
The input terminates with an input 0 as the first input for a test case.
Output
For each test case output three integers r, c and T in one line. Integers r and c
represent the location of the undisputed monarch, where r is the row number and c is the
column number of the tree on which the monarch lives. In case monarchy is disputed, both r
and c are zero. The integer T represents the total number of trees visible to a lord of lords.
Sample Input
3 3
1 2 3
4 5 6
7 0 9
3 4
4 4 4 4
4 4 4 4
4 4 4 4
1 10
5 3 2 1 6 4 2 8 7 1
0
Sample Output
2 2 7
0 0 10
1 5 6
| Author: | rushikesh30 |
| Date Added: | 9-03-2010 |
| Time Limit: | 1 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, TEXT, WSPC |
Comments

Fetching successful submissions

Please register at
Please register at http://bit.ly/DSPPC2_Register to claim prizes and certificates.
The CodeChef Rankings are not
The CodeChef Rankings are not accepted Directly. Some Mal-Practices have been observed and Strict action would be taken.
Well, this was very unlucky
Well, this was very unlucky and sad.Obviously many participants knew the test cases used for submissions and this was most unfair contest. Please take action againts those who've just printed the sample output and Dreamsparks team should ATLEAST ban them, how could you allow someone from admin to participate when he know about testing standards ?