34061번 - 소어그래프 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 263 | 107 | 88 | 38.095% |
문제
정점의 개수가 $N$인 소어그래프(XOR Graph)는 다음과 같이 정의된다.
- 소어그래프는 $0$부터 $N-1$까지의 번호가 붙은 $N$개의 정점을 가진다.
- 각 정점 $i$에 대해, 정점 $i$에서 정점 $i\oplus t$와 정점 $(i\oplus t) +1$로 가는 방향 간선이 존재한다.
- 단, 간선을 통해 이동하려는 도착 정점의 번호가 $N-1$을 초과하는 경우, 해당 간선은 존재하지 않는다.
여기서 $\oplus$ 기호는 Bitwise XOR을 나타낸다.
정점의 개수 $N$, 시작 정점 $x$, 도착 정점 $y$, 그리고 음이 아닌 정수 $t$가 주어질 때, 정점 $x$에서 정점 $y$로 이동하기 위해 지나야 하는 간선의 최소 개수를 구하는 프로그램을 작성하라.
입력
첫째 줄에 정수 $N$, $x$, $y$, $t$가 공백으로 구분되어 주어진다. ($2 \leq N \leq 10^{18}$; $0 \leq x, y < N$; $x \neq y$; $0 \leq t < 2^{20}$)
출력
정점 $x$에서 정점 $y$로 이동하기 위해 지나야 하는 간선의 최소 개수를 출력한다. 만약 정점 $x$에서 정점 $y$로 가는 경로가 존재하지 않는다면 $-1$을 출력한다.
예제 입력 1
4 2 3 2
예제 출력 1
2
예제 입력 2
10 7 9 6
예제 출력 2
-1
예제 입력 3
165321961421 998244353 5029393147 98207
예제 출력 3
8242633
출처
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2025 ��선 J번
- 문제를 만든 사람: minjunnick
- 문제를 검수한 사람: 79brue, evenharder, kipa00, leo020630, man_of_learning, ncy09, seonah
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호