UTPC Contest 12-01-23 Div. 2 (Beginner) |
---|
Закончено |
Zeynep has been craving baklava to satisfy her major sweet tooth. As she's pouring the syrup over the baklava, she wonders: given the locations where she has poured syrup, which piece ends up the sweetest?
Formally, each baklava piece is located at some index $$$(i,j)$$$ on a $$$n \times m$$$ grid, and has some height $$$h_{i,j}$$$. Due to the way the baklava is sliced, the syrup flows at an angle; the syrup can either flow directly up or down to $$$(i \pm 1, j)$$$, or it can flow at a diagonal to either $$$(i-1, j-1)$$$ or $$$(i+1, j+1)$$$. The syrup can only flow to a piece with the same or lower height.
Zeynep pours the syrup on $$$q$$$ locations, and lets the syrup flow completely before pouring again. Can you identify which piece is covered by syrup the most number of times?
The first line contains $$$n, m$$$ and $$$q$$$ ($$$1 \leq n,m \leq 100$$$, $$$1 \leq q \leq 1000$$$), the dimensions of the baklava grid and the number of syrup pours.
The next $$$n$$$ lines each contain $$$m$$$ integers, where the $$$i$$$th line contains the heights $$$h_{i,1}, \ldots, h_{i,m}$$$ ($$$0 \leq h_{i,j} \leq 10^9$$$) of each baklava piece.
The next $$$q$$$ lines contain two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i \leq n, 1 \leq j \leq m$$$), the coordinates of the piece where the $$$i$$$th syrup pour starts.
Output three integers, the coordinates of the sweetest piece $$$(i,j)$$$, as well as the number of times that piece gets covered by syrup. If there are multiple sweetest pieces, pick the one with the smallest row coordinate $$$i$$$, and break further ties with the smallest column $$$j$$$.
5 5 3 7 9 9 9 9 6 6 9 2 8 5 9 5 2 8 4 3 5 2 8 3 9 5 2 8 1 1 3 3 1 5
2 4 3
Название |
---|