연습문제

[한양대 HCPC 2023] ChatGPT의 역작

난이도
Lv. 4
제출
26 명
참가자
3 명
정답률
8.00 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C++ 1초 1024MB
JavaScript 5초 1024MB
Java 3초 1024MB
C 1초 1024MB
Python 5초 1024MB

대회가 다가오는데도 문제를 만들지 못한 하이비는 결국 AI의 힘을 빌려 다음과 같은 문제를 만들었다.

정수 , 길이 의 정수로 이루어진 수열 에 대해, 다음과 같은 함수 를 정의해 보자.

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연산에 대해서는 노트를 참고하자.

이 주어질 때, 이면서 를 찾으면 된다.

하지만 AI가 만들어 준 이 문제가 너무 어려웠던 하이비는 이 문제를 풀지도 못한 채로 내야 할 위기에 처하게 되었다! 하이비를 위해 위 문제의 답을 찾아주자.


노트:

  • a&b는 두 수 의 Bitwise AND를 의미한다. 두 수의 Bitwise AND 연산은 두 수를 이진수로 변환한 뒤, 각 비트별로 두 수가 모두 이라면 을, 아니면 을 적는 연산이다. 예로, 가 된다.
  • a|b는 두 수 의 Bitwise OR을 의미한다. 두 수의 Bitwise OR 연산은 두 수를 이진수로 변환한 뒤, 각 비트별로 두 수 중 하나라도 이라면 을, 아니면 을 적는 연산이다. 예로, 가 된다.
  • a^b는 두 수 의 Bitwise XOR을 의미한다. 두 수의 Bitwise XOR 연산은 두 수를 이진수로 변환한 뒤, 각 비트별로 다르다면 을, 아니면 을 적는 연산이다. 예로, 가 된다.
  • a**b를 의미한다. 즉, 2**64을 의미한다.
  • a mod b로 나눈 나머지를 의미한다. 예로, 이다.
  • 0x는 16진수 표기법을 의미한다. 즉, 0x0123456789ABCDEF이다.
제약조건

입력형식

첫 번째 줄에는 수열의 길이 이 주어진다.

두 번째 줄에는 수열 이 공백으로 구분되어 주어진다.

세 번째 줄에는 수열 이 공백으로 구분되어 주어진다.

출력형식

첫 번째 줄에 문제의 답으로 가능한 의 값을 출력한다.

만약 가능한 답이 여러 가지라면, 그중 아무거나 하나를 출력한다.

만약 가능한 답이 없다면, 을 출력한다.

입력예제1

3 123 12 1283918464548864 456 17 168377826559400929

출력예제1

1283918464548863

이 외에도 등의 답이 가능하다.