Robotic bullfighting P79936


Statement
 

pdf   zip

thehtml

Enough of annoying bulls, poor animals. Bullfights have to modernize, and to this end, we proposed that bulls were substituted by fearsome bull robots, with truck diesel engines, sensors of motion, heat and vision, and an artificial intelligence with a fairly bad mood. Unfortunately, the designed bull robot was a little too dangerous, so after a few nonfatal incidents (it was a really sensible idea to use in those early tests foam rubber horns instead of steel diamond ones), the bullfighters’ union informed us that, or we make the bull a bit more predictable, or the bull is going to be fighted “by our aunt”.

To this end we ask for your help. Write a program that, given an image of w × h pixels as seen by the bull robot, where every pixel is a number between 0 and 255 indicating the intensity of red color at this point in the image, finds out which is the redder square of c × c pixels, i.e., such that the average of the intensities of its pixels is maximum.

Input

Input begins with three natural numbers w, h and c. Follow h lines, each one with w natural numbers between 0 and 255. You can assume 2≤ w,h≤ 500 and 1≤ c≤ min(w, h).

Output

Print the row and the column of the upper-left corner of the square that has the maximum red intensity. If there is more than one square with maximum intensity, print the one with smaller row, and if there are several, the one with smaller column. Both the rows and the columns are numbered starting at 0.

Public test cases

  • Input

    10 10 3
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 9 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

    Output

    2 7

  • Input

    5 5 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

    Output

    0 0

  • Input

    8 8 4
13 42 98 12 32 12 98 98
13 13 41 24 98 17 38 27
12 84 91 34 72 37 12 12
13 49 30 24 12 90 93 21
13 74 23 83 17 47 23 78
13 78 31 78 12 73 18 78
13 72 14 72 47 32 81 83
13 47 23 12 49 48 24 42

    Output

    3 4
    • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++ Python