30883번 - XNOR의 반란 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 114 | 33 | 26 | 36.111% |
문제
PS 문제에는 항상 XOR만 사용된다는 점에 분노한 XNOR이 음이 아닌 정수 $N$개를 모아 반란을 일으키기로 했다!
XNOR은 체계적이기 때문에, 반란을 일으키기 전 반란의 강도를 계산해 보기로 했다. XNOR이 일으키는 반란이기 때문에, 반란의 강도는 주어진 수를 앞에서부터 차례로 XNOR한 결과가 된다. XNOR이 모은 정수들은 모두 부호 없는 $B$비트 정수로 표현할 수 있기 때문에, $B$비트 정수 간의 XNOR을 사용한다.
반란의 강도가 높을수록 성공할 확률이 높아지기 때문에, XNOR은 $N$개의 수 중 하나 이상의 수를 선택해서 반란의 강도를 최대화하기로 했다. 이때 선택된 수의 순서를 바꿀 수는 없다.
입력
첫 번째 줄에 XNOR이 모은 수의 개수 $N$과, XNOR이 사용하는 비트의 수 $B$가 공백으로 구분되어 주어진다. $(1\le N\le 200\, 000;$ $1\le B\le 60)$
두 번째 줄에 XNOR이 모은 $N$개의 음이 아닌 정수 $A_1,A_2,\ldots ,A_N$이 10진수의 형태로 공백으로 구분되어 주어진다. $(0\le A_{i}\lt 2^B)$
출력
첫 번째 줄에 XNOR이 만들어 낼 수 있는 최대 반란의 강도를 출력한다.
예제 입력 1
5 3 1 2 3 4 5
예제 출력 1
7
XNOR이 $[2, 3, 4, 5]$를 선택하면, $((2 \text{ XNOR } 3) \text{ XNOR } 4) \text{ XNOR } 5 = 7$이 된다.
$3$비트 정수이므로, $2^3-1 = 7$보다 더 큰 수를 만들 수는 없다.
예제 입력 2
1 60 1217
예제 출력 2
1217
하나 이상의 수를 선택해야 하므로, 가능한 경우가 하나밖에 없다.
노트
두 수의 Bitwise XNOR 연산은 두 수를 이진수로 변환한 뒤, 각 비트를 비교하여 같으면 $1$, 다르면 $0$을 비트별로 계산하는 연산이다. 예로, $1100_{(2)}\text{ XNOR } 0110_{(2)}=0101_{(2)}$가 된다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호