보물 찾기 Batch 컴파일 명령

최근 지진이 일어난 아드리아해에서는 바다 속에 있던 섬이 나타났다고 합니다. 이 섬은 대부분이 아무것도 없는 황량한 지역이었지만, 흔치 않은 장치가 발견되면서부터 그 가치가 새롭게 조명되기 시작했습니다. 사람들이 이 장치의 이름으로 "oracle"을 붙였기 때문에 저도 그렇게 사용하도록 하겠습니다. "oracle" 장치가 아무런 설명서 없이 등장했기 때문에, 고고학자들과 컴퓨터 전문가들이 이를 해독하기 위해 노력한 결과 이 기계가 어떻게 돌아가는지 찾아내는 데에 성공했습니다.

oracle 기계는 섬에 있는 보물들의 위치를 제공합니다. 섬은 각각 $1$부터 $N$까지의 자연수 번호가 붙은 $N$개의 행과 $N$개의 열로 구성된 격자판으로 나타낼 수 있습니다. 이 중 몇 개의 격자에 보물이 묻혀 있습니다. oracle 기계는 "격자판에서 직사각형 하나가 주어질 때, 이 직사각형 안에 보물이 있는 칸이 몇 개인가?"와 같은 형태의 질의에 답할 수 있습니다.

oracle 기계가 어떠한 크기의 직사각형이 주어져도 정확히 답할 수 있다는 것은 밝혀졌지만, 요구하는 정보가 더욱 명확해질수록 (직사각형의 크기가 작아질수록), oracle 기계가 더 많은 에너지를 사용한다는 것이 밝혀졌습니다. 엄밀히 말하면, 직사각형이 $S$개의 격자를 포함할 때 oracle 기계는 정확히 $1 + N \times N - S$만큼의 에너지를 사용합니다.

해야 할 일

oracle 기계에게 질의를 할 기회가 주어질 때, 섬에서 보물이 있는 모든 위치를 찾아내는 프로그램을 작성하세요. 에너지를 많이 사용하는 것은 좋지 않기 때문에, 적은 에너지를 사용할 수록 좋습니다. 물론 가장 작은 에너지를 사용해야만 점수를 얻을 수 있는 건 아닙니다. 아래의 "채점 기준"을 보시고 여러분의 답안이 얼마나 많은 점수를 얻을 수 있는지 알 수 있습니다.

구현

(주의) 이 문제는 인터렉티브 문제입니다. 안타깝게도 실제 대회와 같은 환경으로 채점 서버를 바꿀 수는 없어서, 함수를 구현하는 방식으로 바꿉니다.

그레이더 함수 : countTreasure()

int countTreasure (int r1, int c1, int r2, int c2);

설명

이 함수는 그레이더에 포함되어 있습니다. 이 함수는 (r1, c1)을 좌측 상단의 모퉁이로, (r2, c2)를 우측 하단의 모퉁이로 하는 직사각형 내에 포함된 보물이 있는 격자의 수를 반환해 줍니다. 이 함수는 O(1) 시간에 동작합니다.

파라미터

• r1 : 직사각형의 가장 왼쪽 위 격자의 행 번호 (1 ≤ r1 ≤ N)
• c1 : 직사각형의 가장 왼쪽 위 격자의 열 번호 (1 ≤ c1 ≤ N)
• r2 : 직사각형의 가장 오른쪽 아래 격자의 행 번호 (r1 ≤ r2 ≤ N)
• c2 : 직사각형의 가장 오른쪽 아래 격자의 열 번호 (c1 ≤ c2 ≤ N)
• 반환값: 직사각형 내 보물이 있는 격자의 수

그레이더 함수 : Report()

void Report (int r, int c);

설명

이 함수는 그레이더에 포함되어 있습니다. 여러분이 countTreasure() 함수를 적절히 호출하여 보물이 들어 있는 모든 칸을 찾아냈다면, 보물이 들어 있는 모든 격자 (r, c)에 대해 이 함수를 호출하셔야 합니다.

보물이 들어 있지 않은 칸에 대해 이 함수를 호출하거나, 이 함수를 호출한 이후에 countTreasure() 함수를 호출하거나, 같은 칸에 대해 두 번 호출한 경우 틀린 답으로 간주하여 0점 처리됩니다.

만약 보물이 한 칸에도 묻혀 있지 않다면 이 함수를 한 번도 호출하면 안 됩니다.

파라미터

• r : 여러분이 구한 답안에서 격자가 들어 있는 칸 중 하나의 행 번호 (1 ≤ r ≤ N)
• c : 여러분이 구한 답안에서 격자가 들어 있는 칸 중 하나의 열 번호 (1 ≤ c ≤ N)

구현해야 하는 함수 : findTreasure()

void findTreasure (int N);

설명

이 함수를 구현하여 제출해야 합니다.

이 함수는 보물이 묻혀 있는 모든 칸의 위치를 알아내기 위하여 그레이더 함수 countTreasure()를 이용해야 하며, 이 정보를 알아내면 Report() 함수를 0번 이상 호출해야 합니다.

파라미터

• N : 격자의 크기 (한 변의 길이)

예제 세션

N = 2이고, 보물이 아래 그림과 같이 묻혀 있다고 가정합시다.

findTreasure()에서는 아래와 같이 그레이더 함수를 호출할 수 있습니다.

제약 조건

• 시간 제한 : 1초
• 메모리 제한 : 256MB
• 1 ≤ N ≤ 100

채점 기준

10개의 채점 데이터가 있으며, 각 데이터에서 최대 10점을 받을 수 있습니다. 만약 여러분의 답이 정확하지 않거나 함수 호출 과정에서 문제가 발생할 시 그 답에 대해서 0점을 받게 됩니다. 답이 정확하다면, 이 데이터에서 받을 점수는 oracle 기계가 여러분의 프로그램에 의해 사용한 에너지의 양 $K$에 따라 결정됩니다.

• $K \le \frac{7}{16} N^4 + N^2$이면 10점
• $K \le \frac{7}{16} N^4 + 2 N^3$이면 8점
• $K \le \frac{3}{4} N^4$이면 4점
• $K \le N^4$라면 1점
• 위의 모두를 만족하지 않는다면 0점

추가적으로, 40점을 받을 수 있는 테스트 데이터에 한해 N이 최대 20입니다.

여러분의 답안은 프로그램이 답을 찍어 맞추더라도(?!) - 즉 countTreasure() 함수를 한 번도 호출하지 않더라도 위 채점 기준대로 점수를 받을 수 있습니다.

테스트용 입력 형식

여기에 주어지는 샘플 그레이더는 입력을 표준 입력(stdin)에서 받아들이는데, 형식은 아래와 같아야 합니다.

• 첫 번째 줄: N
• 2~N+1번째 줄: i번째 줄은 i-1번 행의 격자들의 정보를 0과 1로 구성된 길이가 N인 문자열을 포함해야 합니다. 만약 i행 j열에 보물이 묻혀 있다면 j번째 문자는 1, 그렇지 않다면 0을 입력해야 합니다.

예를 들어, 위의 예시는 다음와 같은 형식을 따라야 한다.

2
01
11

프로그래밍 언어 유의사항

예시를 위해서 솔루션 템플릿을 참조하시오.