30871번 - ChatGPT의 역작 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 409 | 132 | 95 | 33.688% |
문제
대회가 다가오는데도 문제를 만들지 못한 하이비는 결국 AI의 힘을 빌려 다음과 같은 문제를 만들었다.
정수 $x$, 길이 $N$의 정수로 이루어진 수열 $L$과 $R$에 대해, 다음과 같은 함수 $f$를 정의해 보자.
f(x, L[1..N], R[1..N]):
value = x
for i = 1 to N
l = L[i]
r = R[i]
if l ≤ x ≤ r
value = value^(((x|l)+(x&r)*(l^r)) mod (2**64))
return (value >= 0x0123456789ABCDEF)
코드에 적힌 |, &, ^, **, 0x, mod연산에 대해서는 노트를 참고하자.
$L$과 $R$이 주어질 때, $f(x,L,R) =\text{False}$이면서 $f(x+1,L,R) =\text{True}$인 $x$를 찾으면 된다.
하지만 AI가 만들어 준 이 문제가 너무 어려웠던 하이비는 이 문제를 풀지도 못한 채로 내야 할 위기에 처하게 되었다! 하이비를 위해 위 문제의 답을 찾아주자.
입력
첫 번째 줄에는 수열의 길이 $N$이 주어진다. $(1\le N\le 200\, 000)$
두 번째 줄에는 수열 $L_1,L_2,\ldots ,L_N$이 공백으로 구분되어 주어진다.
세 번째 줄에는 수열 $R_1,R_2,\ldots ,R_N$이 공백으로 구분되어 주어진다. $(1\le L_i\le R_i\le 10^{18})$
출력
첫 번째 줄에 문제의 답으로 가능한 $x$의 값을 출력한다. $(0\le x\le 10^{18})$
만약 가능한 답이 여러 가지라면, 그중 아무거나 하나를 출력한다.
만약 가능한 답이 없다면, $-1$을 출력한다.
예제 입력 1
3 123 12 1283918464548864 456 17 168377826559400929
예제 출력 1
1283918464548863
이 외에도 $81\, 985\, 529\, 216\, 489\, 760$ 등의 답이 가능하다.
노트
a&b는 두 수 $a$와 $b$의 Bitwise AND를 의미한다. 두 수의 Bitwise AND 연산은 두 수를 이진수로 변환한 뒤, 각 비트별로 두 수가 모두 $1$이라면 $1$을, 아니면 $0$을 적는 연산이다. 예로, $1100_{(2)}\text{ & } 0110_{(2)}=0100_{(2)}$가 된다.a|b는 두 수 $a$와 $b$의 Bitwise OR을 의미한다. 두 수의 Bitwise OR 연산은 두 수를 이진수로 변환한 뒤, 각 비트별로 두 수 중 하나라도 $1$이라면 $1$을, 아니면 $0$을 적는 연산이다. 예로, $1100_{(2)}\text{ | } 0110_{(2)}=1110_{(2)}$가 된다.a^b는 두 수 $a$와 $b$의 Bitwise XOR을 의미한다. 두 수의 Bitwise XOR 연산은 두 수를 이진수로 변환한 뒤, 각 비트별로 다르다면 $1$을, 아니면 $0$을 적는 연산이다. 예로, $1100_{(2)}\text{ ^ } 0110_{(2)}=1010_{(2)}$가 된다.a**b는 $a^b$를 의미한다. 즉,2**64는 $2^{64} = 18\,446\,744\,073\,709\,551\,616$을 의미한다.a mod b는 $a$를 $b$로 나눈 나머지를 의미한다. 예로, $7 \bmod 3 = 1$이다.0x는 16진수 표기법을 의미한다. 즉,0x0123456789ABCDEF는 $0123456789ABCDEF_{(16)}=81\, 985\, 529\, 216\, 486\, 895$이다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호