Informatica Online Judge

  Matrix Search I (Tiny) (Interactive Judge) [0707 / 02C3]

Time Limit(Test case) : 200(ms)
Number of users who solved : 74   Total Tried : 92


The Champion of this Problem (C++) : gs18012 - 0ms / 368byte
My Best Submission (C++) : N/A

[]

Background

행렬에서 원하는 원소를 빠르게 찾는 것이 목적이다.

이 문제에 주어진 행렬은 다음과 같은 특징이 있다.

1) (i, j)의 원소보다 (i, j+1)의 원소가 반드시 같거나 크다.
2) (i, j)의 원소보다 (i+1, j)의 원소가 반드시 같거나 크다.

다음과 같은 3행 3열의 행렬을 보자.


1 3 5
2 4 7
3 5 8


이 행렬의 위 조건 1), 2)를 만족한다. 다음 행렬을 보자.


1 3 3
2 2 7
3 5 8


위 행렬의 2,2의 값은 조건 2를 만족하지 않으므로 잘못된 행렬이다.

이 문제는 Interactive Judge의 기본 스타일 문제이다. 행렬값을 입력받는 것이 아니라. 행렬이 정의된 헤더파일을 반드시 포함하고 시작하시오.

프로그램 시작시에 #include "lib.h"라고 적어야 한다.

그리고 lib.h에는 다음과 같은 함수가 정의되어 있다.

int function(int, int);

이 함수는 행렬의 i행, j열의 원소를 구해준다. (단 가장 왼쪽 위는 1,1이다. 가장 오른쪽 아래는 100, 100이다.)

어떤 값 k를 입력받아서 행렬내에 존재하는 k의 위치를 찾으시오.

단, k가 여러 개 존재할 경우, 행의 값이 작은 k를, 같은 행이라면 열의 값이 작은 k의 좌표를 출력하시오.

Input

첫 번째 줄에 찾고자하는 k의 값이 입력된다. (단 k는 30,000 이하의 자연수)

* function함수의 사용 횟수제한 10,000회

사용횟수 이상 호출하게 되면 잘못된 값을 리턴한다.

Output

k가 존재하는 행과 열을 공백으로 구분하여 출력한다. 단, 행렬에 k값이 없을 경우는 -1을 출력한다.

IO Example

없음.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]