31226번 - 고슴도치 그래프 2 다국어인터랙티브
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 1024 MB | 209 | 13 | 9 | 5.085% |
문제
이 문제는 인터랙티브 문제입니다.
고슴도치 귀엽지 않나요?
귀여운 고슴도치!
키파는 "성게 그래프"도 있는데 이렇게 귀여운 고슴도치에 대응하는 그래프가 없는 것은 아무래도 말이 안 된다고 생각해서, 고슴도치 그래프를 만들기로 했습니다.
고슴도치 그래프는 다음과 같은 두 가지 성질을 만족하는 방향 없는 연결 그래프입니다. 이 그래프에는 self-loop(한 정점 $v$와 같은 정점인 $v$를 연결하는 간선)와 multiedge(서로 다른 두 정점 $v$와 $w$에 대해 $v$와 $w$를 연결하는 서로 다른 간선 $e_{1}$과 $e_{2}$)가 없습니다.
- 사이클이 정확히 하나 존재합니다. 이 사이클을 고슴도치의 몸통이라고 부르겠습니다. 몸통의 크기는 사이클에 속한 정점의 개수입니다. 사이클이 항상 존재하기 때문에 몸통의 크기는 항상 $3$ 이상이라는 점에 유의하세요.
- 사이클에 속하지 않은 정점의 차수가 $1$입니다.
키파는 고슴도치 그래프를 열심히 키운 결과 각 그래프가 $V = 10^{6}$개의 정점으로 이루어진 고슴도치 그래프를 총 $N$개 가지게 되었습니다. 키파는 각 고슴도치 그래프를 다음과 같은 방법으로 어루만져 주기로 했습니다.
- 각 노드에 붙어 있는 간선의 방향을 한 방향으로 정하되, 모든 노드가 나가는 방향의 간선을 정확히 하나 가지도록 정합니다. 임의의 고슴도치 그래프에 대해, 간선의 방향을 위 조건을 만족하도록 정하는 것이 항상 가능함을 증명할 수 있습니다.
- 다음을 최대 $M = 900$번 반복합니다.
- 정점 $v$와 $5 \times 10^{18}$ 이하의 아무 양의 정수 $x$를 고릅니다.
- $v$에서 화살표를 $x$번 따라가며 고슴도치 그래프를 쓰다듬습니다. 모든 노드가 나가는 방향의 간선이 하나 있기 때문에 도착 노드는 하나로 정해지며, 이 도착 노드가 어디인지 알 수 있습니다.
과정 1은 키파가 이미 임의로 방향을 정했습니다.
키파는 고슴도치 그래프를 어루만져 주는 것뿐만 아니라 각 고슴도치 그래프의 몸통의 크기를 알고 싶어했습니다. 하지만 키파는 이걸 생각하기에는 머리가 너무 아팠기 때문에, 과정 2를 여러분에게 맡기기로 했습니다.
여러분은 각 고슴도치 그래프에 대해 과정 2를 시행한 후 얻은 정보로 각 고슴도치의 몸통의 크기를 알아내야 합니다.
입력
첫째 줄에 $10$ 이하의 양의 정수 $N$이 주어집니다. 그러고 나면 인터랙션이 시작됩니다.
인터랙션
여러분은 채점 시스템에게 다음과 같은 질의를 할 수 있습니다.
? v x: 정점 $v$에서 화살표를 $x$번 따라가서 도착한 노드 번호를 돌려줍니다. $1 \leq v \leq V$, $1 \leq x \leq 5 \times 10^{18}$를 만족해야 합니다. 이 질의는 그래프 당 최대 $M$번 할 수 있으며, 결과는 도착 정점 번호를 나타내는 $1$ 이상 $V$ 이하의 정수입니다.! s: 현재 어루만지고 있는 그래프의 몸통의 크기 $s$를 채점 프로그램에게 알려주는 질의입니다. 그래프 당 한 번 질의할 수 있으며, 결과는 몸통의 크기가 맞았음을 의미하는 $1$이거나 몸통의 크기가 틀렸음을 의미하는 $-1$입니다. 크기가 맞은 경우 다음 그래프로 넘어갑니다.
질의를 출력한 후에는 표준 출력 버퍼를 flush해 주어야 합니다. 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같습니다.
- C:
fflush(stdout) - C++:
std::cout << std::flush - Java:
System.out.flush() - Python:
sys.stdout.flush() - Kotlin:
System.out.flush()
어떤 질의에서든지 음수를 응답으로 받았을 경우 프로그램을 즉시 정상 종료해야 하며, 이 경우 틀렸습니다를 받습니다. 프로그램을 즉시 종료하지 않을 경우 다른 결과를 받을 수 있음에 주의하세요.
$N$개의 ! 질의에서 모두 $1$을 받은 경우 프로그램을 종료하면 그 테스트 케이스에 대해서는 맞은 것으로 처리됩니다.
예제 입력 1
1 3 7 10 1
예제 출력 1
? 1 2 ? 2 5 ? 10 11 ! 11
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호