| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 47 | 7 | 7 | 31.818% |
서울과학고대유적 탐험하기 1, 2 문제는 질문의 유형을 제외한 모든 사항이 동일합니다.
이 문제는 인터랙티브 문제입니다.
최근 고고학자들은 "서울과학고대유적"이라는 고대 유적을 발견하였다!
서울과학고대유적은 1ドル$번부터 $N$번까지 $N$개의 유적들과 서로 다른 두 유적을 연결하는 $N-1$개의 도로로 연결된 트리 형태로 표현할 수 있다. 모든 도로는 양방향으로 이동할 수 있고, 도로를 이용해 모든 유적 사이를 이동할 수 있다.
서울과학고대유적의 도로들은 세월이 지나면서 사라진 지 오래지만, 도로에 대한 정보를 얻을 수 있는 탐험록이 전해져 내려오고 있다. 탐험록은 $N$개의 탐험 기록으로 이루어져 있고, 각 탐험 기록은 $N$개의 유적들을 특정한 순서로 방문한 기록이다.
고고학자들이 서울과학고대유적 탐험록을 분석한 결과, $i$번째 탐험 기록은 다음과 같은 방법으로 유적들을 방문한 결과임을 밝혀냈다.
단, 위의 방법으로 탐험을 진행하였을 때 시작점에 관계 없이 모든 유적을 방문하고 탐험록에 기록함을 증명할 수 있다.
서울과학고대유적의 구조를 알아내기 위해 당신은 다음과 같은 질문을 할 수 있다:
? i j: $i$번 탐험 기록에 기록된 유적의 순서 중 $j$번째로 기록된 유적의 번호를 질문한다.이때, 서울과학고대유적의 구조를 알아내는 프로그램을 작성하자.
첫 번째 줄에 유적의 수 $N$이 주어진다.
질문을 위해서는 다음의 형식으로 출력한 뒤 출력 버퍼를 비워야 한다.
? i j
이후, 입력으로 정수 $k$를 입력받아야 한다. 이 수는 $i$번째 탐험 기록에 $j$번째로 기록된 유적의 번호를 나타낸다. 1ドル \le i, j \le N$여야 하며, 1ドル \le k \le N$임이 보장된다.
서울과학고대유적의 구조를 알아냈다면, 다음과 같은 형식으로 출력한 뒤 버퍼를 비워야 한다.
!
u[1] v[1]
u[2] v[2]
...
u[N-1] v[N-1]
이는 서울과학고대유적의 $i$번째 도로가 $u[i]$번 유적과 $v[i]$번 유적을 잇는다는 것을 의미한다. (1ドル \le i \le N-1$) 도로를 출력하는 순서, $u[i]$와 $v[i]$의 순서는 상관없다.
질문은 최대 20ドル,000円$회 할 수 있고, 20ドル,000円$회 초과로 질문하게 된다면 채점 결과로 틀렸습니다를 받게 된다.
서울과학고대유적의 구조를 출력한 후, 당신의 프로그램은 즉시 종료해야 한다. 만약 프로그램이 곧바로 종료하지 않는다면 예상치 못한 채점 결과를 받을 수 있다.
서브태스크 2에서는 사용한 질문의 개수 $Q$에 대하여 부분 점수를 받을 수 있다.
모든 테스트케이스에서, $Q/N$의 최대값을 $K$라 하자. 서브태스크 2에서 얻는 점수는 $K$의 값에 따라 다음과 같이 결정된다.
5 2 5 5 4
? 1 3 ? 1 5 ? 2 4 ? 4 1 ! 1 3 3 2 3 4 1 5
예제는 이해를 돕기 위해 개행 간격을 의도적으로 조절한 것으로, 실제 입출력에서는 빈 줄을 입력받거나 출력하지 않아야 한다.
예제의 데이터에 해당되는 구조에서 기록된 유적들은 순서대로 다음과 같다.
출력 버퍼를 비우는 방법은 다음과 같다.
fflush(stdout)std::cout << std::flushSystem.out.flush()sys.stdout.flush()이외의 언어에 대해서는 언어별 명세를 참고해야 한다.
School > 서울과학고등학교 > SciOI 2024 H1번