아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

King of the Hill

시간 제한5초메모리 제한1024 MB

요약
각 칸의 높이가 서로 다른 n x n 격자에서 질의 10n+100회만으로 유일한 전역 최댓값을 찾는다.
난이도

보통10점 중 7점

유형
이분 탐색, 분할 정복, 행렬
정답자
아직 제출이 없습니다

문제

The king of Belle Aire People's Country has come up with a new plan: he has heard about the popular phenomenon called "King of the Hill", and he would like to become one as well. To do so, he has ordered you to raise a flag on the highest hill in his square kingdom, which has dimensions n×nn \times n. You are given a very expensive (it is gold- and jewel-embedded) satellite-based height-measuring system. This equipment is highly accurate: the heights on every location in the kingdom are represented with distinct integers. However, to cut costs, you are only allowed to take 10n+10010n+100 measurements before reporting back to the king.

Furthermore, you know for certain that there is only a single point that is the absolute highest: this is the only point for which its height is larger than the (up to) four orthogonally adjacent points that lie inside the kingdom. In other words, there are no local maxima besides the global maximum.

예제2

  1. 예제 1

    입력
    3

3

9

4

8

7
    예상 출력
    
? 2 1

? 2 2

? 2 3

? 3 2

? 1 2

! 9

  2. 예제 2

    입력
    4

600000000

864213579

864297531

987654321

123456789

975318642
    예상 출력
    
? 3 3

? 2 3

? 2 2

? 1 2

? 1 1

? 1 3

! 987654321