\documentclass[12pt]{article}
\input{iati_structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\usepackage[english]{babel}

\begin{document}
	
\renewcommand{\headerLang}{English}
\renewcommand{\problemName}{AB03. MINIMUM POINT}

\renewcommand{\headerLeft}{IATI Day 0, Senior group}
\renewcommand{\headerRightFirst}{XVII INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS}
\renewcommand{\headerRightSecond}{ONLINE 2026}

\renewcommand{\tl}{$0.1$ sec.}
\renewcommand{\ml}{$1024$ MB}
\problem{Task \problemName}

Our somewhat forgotten heroine \textbf{D}eni got herself into a new adventure. She got lost in a labyrinth shaped like a grid, filled not with just anything -- but with numbers. The grid has dimensions $N \times M$, and the numbers in it are positive integers. \textbf{D}eni is a smart girl, so she has figured out that the exits of the grid are located at the so-called \textit{local minimum} points. A \textit{local minimum} point of the grid is a cell whose value is strictly smaller than the values of its neighbors. Two cells are neighbors if they share a common side.

\textbf{D}eni can explore the value of arbitrary cells in the grid and wants to find an exit from the grid using as few explorations as possible. Write a program \texttt{\textbf{locmin}} that finds a \textit{local minimum} point of an unknown grid.

\subsection{Implementation details}
You should implement the function \texttt{find\_locmin\_point}:
\begin{lstlisting}
 std::pair<int, int> find_locmin_point(int N, int M)
\end{lstlisting}
\begin{itemize}
	\item $N$, $M$: the number of rows and the number of columns of the grid.
\end{itemize}

This function is called once for each test case and has to return an ordered pair containing the row number and the column number of a \textit{local minimum} point. Rows are numbered consecutively from $1$ to $N$, and columns -- consecutively from $1$ to $M$. In order to do this, your program can call the jury function \texttt{value}:
\begin{lstlisting}
 long long value(int r, int c)
\end{lstlisting}
\begin{itemize}
	\item $r$, $c$: the row and the column of the cell you are exploring.
\end{itemize}

The function will return the value of the explored cell. If the parameters do not specify a valid cell in the grid, you will receive \texttt{Wrong answer} for the corresponding test. The complexity of this function is constant. You may call this function at most $N \times M$ times; otherwise you will also receive \texttt{Wrong answer}.

\subsection{Constraints}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq N, M \leq 500$.
	\item The values in the grid are integers in the interval $[1; 10^{18}]$.
	\item It is guaranteed that there exists at least one \textit{local minimum} point in the grid.
	\item \textbf{There are no neighboring cells in the grid with equal values.}
\end{itemize}

\newpage
\subsection{Subtasks}
\begin{table}[ht]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Subtask} & \textbf{Points} & $N$ & \textbf{Other constraints}\\
		\hline
		$0$ & $0$ & $-$ & The grid from the sample interaction. \\ 
		\hline
		$1$ & $21$ & $=1$ & -- \\ 
		\hline
		$2$ & $79$ & $\leq 500$ & {There are tests for which the jury’s program is \textbf{adaptive} -- in them there is no fixed grid in advance; instead it is constructed dynamically depending on the performed explorations.} \\ 
		\hline
	\end{tblr}
	\caption*{The points for a given subtask are obtained only if all the tests for it are \textbf{successfully} passed, and are equal to the minimum score of a test in it multiplied by the points of the subtask.}
\end{table}
\FloatBarrier

\subsection{Scoring}
Each test receives a score, which is a real number between $0$ and $1$ inclusive. If a test has a positive score, it is considered \textbf{successfully} passed for your solution. A test has a positive score if you correctly find a \textit{local minimum} point in the grid within the memory and time limits. Let $cnt$ denote the number of calls to the function \texttt{value} for a given test; then the score of the test is calculated as follows:

\begin{itemize}
	\item Subtask $1$.
	\begin{itemize}
		\item If $cnt < 30$, then the score is $1$.
		\item If $30 \leq cnt < 300$, then the score is $\min(\frac{30}{cnt}, 1)$.
		\item If $cnt \geq 300$, then the score is $0.1$.
	\end{itemize}
	\item Subtask $2$.
	\begin{itemize}
		\item If $cnt < 2026$, then the score is $1$.
		\vspace{0.3em}
		\item If $2026 \leq cnt < 5000$, then the score is $\min((\frac{2026}{cnt})^{\max(\frac{4000}{cnt}, 1)}, 1)$.
		\vspace{0.3em}
		\item If $5000 \leq cnt < 10000$, then the score is $\min((\frac{2026}{cnt})^{1.2}, 0.4)$.
		\vspace{0.3em}
		\item If $cnt \geq 10000$, then the score is $0.1$.
	\end{itemize}
\end{itemize}

\subsection{Sample interaction}
Let us have the following grid with $3$ rows and $4$ columns:
\begin{tblr}{|c|c|c|c|}
	\hline
	5 & 3 & 5 & 6 \\
	\hline
	10 & 6 & 4 & 10 \\
	\hline
	2 & 9 & 8 & 2 \\
	\hline
\end{tblr}

\begin{table}[H]
	\begin{tblr}{|c|c|}
		\hline
		\textbf{Contestant action} & \textbf{Jury's action} \\
		\hline
		& \texttt{find\_locmin\_point(3,4)} \\
		\hline
		\texttt{value(1, 2)} & \texttt{return 3} \\
		\hline
		\texttt{value(1, 1)} & \texttt{return 5} \\
		\hline
		\texttt{value(1, 3)} & \texttt{return 5} \\
		\hline
		\texttt{value(2, 2)} & \texttt{return 6} \\
		\hline
		\texttt{return \{1, 2\}} & \\
		\hline
	\end{tblr}
\end{table}

\subsection{Sample grader}
Input format:
\begin{itemize}
	\item line $1$: two positive integers -- the number of rows $N$ and the number of columns $M$;
	\item line $2$-$(N+1)$: $M$ positive integers specifying the values in the grid in order from the first row and first column to the last row and last column.
\end{itemize}

Output format:
\begin{itemize}
	\item line $1$: two integers -- the returned ordered pair of the call.
\end{itemize}
	
\end{document}