시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 177 | 33 | 21 | 20.000% |
이제부터 여러분은 교준이와 간단한 게임을 하게 된다.
교준이는 마음속으로, 1부터 N까지 N개의 자연수로 이루어진 수열 A를 생각한다. 교준이는 여러분에게 자연수 N만 알려준다. 아직 여러분은 수열 A를 정확히 알지 못한다.
여러분은 교준이 마음속에 있는 수열 A를 알아내기 위하여, 교준이에게 다음과 같은 질문을 할 수 있다.
최소한의 질문으로 수열 A를 정확하게 알아내는 것이 이 게임의 목표이다. 교준이와 본 게임을 진행하는 프로그램을 작성하시오.
여러분의 프로그램은 제공되는 "SORT.h
" 파일을 include 해야 한다.
Grader에서 기본으로 제공하는 함수는 다음과 같다.
bool compare(int a, int b)
true
를 리턴한다. 아닌 경우에는 false
를 리턴한다.Wrong Answer [1]
"라고 판정한다.Wrong Answer [2]
"라고 판정한다. Sample Grader는 "Wrong Answer [2]"를 판정하지 않는다.void answer(int a, int b)
answer(a, b)
를 호출해야 한다.Wrong Answer [3]
"라고 판정한다.Wrong Answer [4]
"라고 판정한다.Wrong Answer [5]
"라고 판정한다.Wrong Answer [6]
"라고 판정한다.여러분은 다음과 같은 함수를 작성해야 한다.
void init(int T, int N)
void sorting()
Grader가 실행 도중, "틀렸습니다"라고 판정한 경우, 그 즉시 프로그램은 종료된다.
여러분은 제출할 소스 파일 안에서 다른 변수나 함수 등을 자유롭게 선언할 수 있다. 다만 입출력 함수를 호출하거나 파일에 접근하는 행위는 금지된다. 또한 Grader의 취약점이나 포인터를 이용하여, Grader의 숨겨진 변수에 접근하거나, 점수를 조작하는 등의 불법적 행위를 할 경우, 실격 처리될 수 있음에 유의하라.
여러분이 작성한 소스 코드를 테스트하기 위하여, Sample Grader가 제공된다. 제공되는 Sample Grader는 실제 채점에 활용되는 Grader와 다를 수 있다.
Sample Grader는 다음과 같은 정보를 Standard Input을 통해 읽는다. 여러분은 어떠한 입력도 받으면 안된다.
첫 번째 줄에 교준이와 할 게임의 총 판 수와 교준이가 생각한 수열 A의 길이를 의미하는 자연수 T, N이 공백을 사이에 두고 주어진다.
두 번째 줄부터 T개의 줄에 걸쳐, 수열 A를 나타내는 N개의 자연수가 공백을 사이에 두고 주어진다.
Sample Grader는 다음과 같은 정보를 Standard Output을 통해 출력한다. 여러분은 어떠한 출력도 하면 안된다.
여러분이 T판의 게임에서 전부 수열 A를 정확하게 알아낸 경우 Sample Grader는 "Accept. Max Questions = %d
"의 형태로 출력한다. 이때, "%d
"는 여러분이 게임 한 판에서 함수 compare
의 최다 호출 횟수를 나타내는 정수이다.
Sample Grader가 "틀렸습니다"라고 판정한 경우 Sample Grader는 "Wrong Answer [4]
"와 같은 형태로 출력한다.
2 4 1 2 3 4 3 1 4 2
Accept. Max Questions = 1
다음은 위의 입출력 예제에 대해서, Sample Grader와 Interaction하는 과정을 나타낸 것이다.
SORT.cpp |
Grader | 설명 |
---|---|---|
T = 2, N = 4 |
Grader에서 T와 N의 값을 읽어들인다. | |
init(T = 2, N = 4) 호출 |
init 함수는 초기에 한 번만 호출된다. |
|
A = {1, 2, 3, 4} |
||
sorting() 호출 |
||
compare(1, 2) 호출 |
||
return true |
A의 2번째 수는 1번째 수보다 크므로 Grader는 true 를 리턴한다. |
|
compare(1, 3) 호출 |
||
return true |
||
compare(3, 4) 호출 |
||
return true |
||
compare(2, 3) 호출 |
||
return true |
||
answer(2, 2) 호출 |
||
answer(4, 4) 호출 |
||
answer(1, 1) 호출 |
||
answer(3, 3) 호출 |
||
sorting() 종료 |
여러분은 A = {1. 2, 3, 4}라고 예상했고, 이는 교준이의 수열과 일치한다. | |
A = {3, 1, 4, 2} |
||
sorting() 호출 |
||
answer(1, 3) 호출 |
||
answer(2, 1) 호출 |
||
answer(3, 4) 호출 |
||
answer(4, 2) 호출 |
||
sorting() 종료 |
여러분은 A = {3, 1, 4, 2}라고 예상했고, 이는 교준이의 수열과 일치한다. | |
Accept. Max Questions = 4 |
위의 Interaction 과정은 실제 정해와 전혀 관련이 없으며, 단지 이해를 돕기 위해 만든 예시이다. 위 예시는 교준이와 게임 두 판을 하면서, 두 번 모두 우연히 교준이의 수열을 정확하게 맞추었다.
C++17, C++14