35304번 - 다리 건설 계획 점수다국어투 스텝
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 52 | 12 | 10 | 43.478% |
문제
KSA 행성에는 $N$개의 섬이 있다. 각 섬에는 $1$번부터 $N$번까지 번호가 붙어 있으며, $i$번 섬은 $w_i$만큼의 자원을 가지고 있다. 자원량이 같은 서로 다른 두 섬은 존재하지 않는다. 섬들 사이에는 두 섬을 양방향으로 연결하는 $N-1$개의 수중 통로가 존재하고, 수중 통로만을 이용하여도 임의의 두 섬 사이를 이동할 수 있음이 보장된다. 즉, 섬과 수중 통로의 구조는 트리를 이룬다.
다른 행성에서는 KSA 행성의 수중 통로가 보이지 않는다는 사실을 깨달은 KSA 행성의 왕 Alice는 두 섬을 양방향으로 연결하는 $N-1$개의 지상 다리를 추가로 건설할 계획을 세우고 있다. 이때 다리들만을 이용해서도 임의의 두 섬 사이를 이동할 수 있어야 한다. 즉, 다리의 구조 또한 트리를 이루어야 한다.
Alice의 다리 건설이 완료되면, Automata 행성의 왕 Bob이 정보를 알아내는 과정이 시작된다. 이때 섬의 번호는 임의로 재설정되며, 이후 Bob이 관찰하거나 사용하는 모든 섬 번호는 이 재설정된 번호 체계를 따른다.
Bob은 Alice가 건설한 지상 다리만을 보고 모든 $1 \le i,j \le N$에 대해 $x(i,j)$를 알아내어야 한다. 여기서
$x(i, j) = $ 수중 통로만을 이용하여 $i$번 섬에서 $j$번 섬으로 이동하는 유일한 단순 경로 위에서 자원량이 최대인 섬의 번호
를 의미한다. 이때 출발 섬의 번호 $i$, 도착 섬의 번호 $j$, 그리고 자원량이 최대인 섬의 번호는 모두 재설정된 번호 기준이며, $i$번 섬에서 $j$번 섬으로 이동하는 경로에는 $i$번 섬과 $j$번 섬도 포함된다.
Bob은 추가적인 정보를 위해 모든 $x(i,j)$를 알아내기 전에 다음 질문을 최대 $100$번 할 수 있다.
?$i$ $j$ : $x(i,j)$가 무엇입니까?
행성들 간의 소통은 매우 큰 비용이 들기 때문에, 질문 횟수가 적을수록 높은 점수를 획득한다.
투 스텝
당신의 프로그램은 채점 데이터 하나당 두 번 실행된다. 첫 번째 실행에서는 Alice의 역할을, 두 번째 실행에서는 Bob의 역할을 수행해야 한다.
입력의 첫 번째 줄에는 실행 단계를 의미하는 정수 $S$가 주어진다. $S=1$인 경우 Alice, $S=2$인 경우 Bob의 역할을 수행해야 함을 의미한다.
Alice의 역할
입력
입력은 하나 이상의 테스트 케이스로 이루어져 있다. 두 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 아래와 같이 주어진다.
각 테스트 케이스의 첫 번째 줄에는 정수 $N$이 주어진다.
두 번째 줄에는 각 섬의 자원량을 나타내는 $N$개의 정수 $w_1, w_2, \cdots, w_N$이 공백으로 구분되어 주어진다.
다음 $N-1$개의 줄에는 각 수중 통로가 잇는 두 섬의 번호 $u$, $v$가 공백으로 구분되어 주어진다.
출력
$N-1$개의 줄에 걸쳐 건설할 지상 다리가 잇는 두 섬의 번호를 공백으로 구분하여 출력한다. 단, 지상 다리를 출력하는 순서와 각 지상 다리가 잇는 두 섬의 번호를 출력하는 순서는 상관없다.
Bob의 역할
인터랙션
입력은 하나 이상의 테스트 케이스로 이루어져 있다. 두 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 아래와 같이 주어진다.
각 테스트 케이스의 첫 번째 줄에는 섬의 개수 $N$이 주어진다.
다음 $N-1$개의 줄에는 Alice가 건설한 지상 다리가 잇는 두 섬의 번호 $u$, $v$가 공백으로 구분되어 주어진다. $u$와 $v$는 재설정된 번호 기준이며, Alice가 출력한 다리의 순서와 Bob이 입력받는 다리의 순서는 다를 수 있음에 유의하라.
추가적인 정보를 위해 아래 쿼리를 출력하면, 다음 줄에 $x(i,j)$의 값이 입력으로 주어진다. 이 쿼리는 하나의 테스트 케이스에서 최대 $100$번만 사용할 수 있다.
?$i$ $j$ ($1 \le i, j \le N$)
답을 제출하려면 !를 출력한 뒤, 그 다음 줄부터 $N$개의 줄에 걸쳐 답을 출력한다. $N$개의 줄 중 $i$번째 줄에는 $x(i,1), x(i,2), \cdots, x(i,N)$을 공백으로 구분하여 출력해야 한다. 이 쿼리는 질문한 것으로 세지 않으며, 출력한 직후 해당 테스트 케이스에 대한 인터랙션은 종료���다.
마지막이 아닌 테스트 케이스에 대한 상호작용이 종료되었다면 즉시 다음 테스트 케이스에 대한 상호작용으로 넘어가야 하고, 마지막 테스트 케이스에 대한 상호작용이 종료되었다면 즉시 프로그램을 종료해야 한다.
단, 한 테스트 케이스에서 $100$회 초과로 질문한 경우 허용된 질문 횟수를 넘겼다는 의미로 쿼리에 대한 답변 대신 $-1$이 입력으로 주어진다. 이 경우 여러분의 프로그램은 즉시 종료되어야 하며, 이 경우 틀렸습니다를 채점 결과로 받게 된다.
제한
- $S \in \{1, 2 \}$
- $1 \le T \le 100$
- $2 \le N \le 100$
- $1 \le u < v \le N$
- $1 \le w_i \le 10^9$
- $i \ne j$이면 $w_i \neq w_j$
점수
각 채점 데이터에 대해서, 모든 테스트 케이스 중 가장 많은 질문을 한 경우의 질문 횟수를 $Q$라고 하자. 해당 채점 데이터에서의 점수는 아래와 같다.
| 번호 | 점수 | 제한 |
|---|---|---|
| 1 | 25 |
$60 < Q \leq 100$ |
| 2 | 37 |
$20 < Q \leq 60$ |
| 3 | 50 |
$4 < Q \leq 20$ |
| 4 | 62 |
$Q = 4$ |
| 5 | 75 |
$Q = 3$ |
| 6 | 100 |
$Q \le 2$ |
제출의 점수는 모든 채점 데이터에서의 점수 중 최솟값이다. 단, 문제의 제한 안에 올바른 상호작용을 통해 답을 출력하지 못하면 예상치 못한 채점 결과를 받을 수 있다.
예제 입력 1
1 2 4 3 5 9 4 1 2 2 3 2 4 2 10 1 1 2
예제 출력 1
1 4 2 3 3 4 1 2
$S = 1$이므로 Alice의 역할을 수행해야 한다.
예제 입력 2
2 2 4 1 3 1 4 2 3 4 1 2 1 2 2
예제 출력 2
? 2 3 ? 1 2 ! 1 1 1 1 1 2 4 4 1 4 3 4 1 4 4 4 ? 1 2 ! 1 2 2 2
$S = 2$이므로 Bob의 역할을 수행해야 한다.
첫 번째 테스트 케이스에서, 첫 번째 실행에서의 $1, 2, 3, 4$번 정점은 순서대로 $2, 4, 1, 3$번 정점으로 재설정되었다.
두 번째 테스트 케이스에서, 첫 번째 실행에서의 $1, 2$번 정점은 순서대로 $2, 1$번 정점으로 재설정되었다.
노트
당신의 프로그램은 무언가를 출력한 후 즉시 출력 버퍼를 비워야 한다. 다음은 언어별 출력 버퍼를 비우는 방법이다.
- C —
fflush(stdout) - C++ —
std::cout.flush() - Python —
sys.stdout.flush() - Java —
System.out.flush() - 그 외의 언어는 각 언어의 Documentation을 참고한다.
또한, 예제의 빈 줄은 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 추가된 것이며, 실제 입출력에는 빈 줄이 나타나지 않는다.
출처
School > 한국과학영재학교 > 2026 KSA Automata Winter Contest J번
- 문제를 만든 사람: mickeyjung
- 문제를 검수한 사람: bennyk0406, edward3378, flakepowders, raehwan0418, sadtreap, utilforever
채점 및 기타 정보
- 100점 이상을 획득해야 를 받는다.
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호