| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 307 | 22 | 9 | 7.200% |
AI Network에서 일하는 루노(Runo)들은 이진수를 사용하며, 이진수 표현에 1ドル$이 많은 수를 좋아한다.
루노들을 관리하는 아인(AIN)이는 루노들의 동기 부여를 위해 앞으로 $N$일간 날마다 가장 열심히 일한 루노에게 "오늘의 루노상"을 수여하려고 한다. 이 상의 상품은 루노들이 좋아할 법한 이진수 표현에 1ドル$이 많은 수이다.
어떤 수를 상품으로 줘야 할지 고민하던 아인이는 본인이 임의로 수를 선택하는 것은 참 힘든 일임을 깨닫고, 다음 $N$일 동안 매일 하나의 정수를 배달해 주는 서비스를 구독했다. 앞으로 $i$번째 날에 받을 수를 $V_i$라고 하자.
아인이는 매일 그날까지 모은 수들을 보고, 다음의 방식으로 루노들에게 줄 상품을 만든다.
아인이는 이렇게 만들 수 있는 수 중에서 이진수 표현에 1ドル$이 가장 많은 수를 하나 선택해 상품으로 주려고 한다.
앞으로 $N$일간, 날마다 아인이가 상품으로 선택할 수 있는 수를 하나 구해 보자.
첫 번째 줄에 아인이가 루노들에게 상을 주려는 일수이자 정수 배달 서비스를 구독하는 일수 $N$이 주어진다.
다음 $N$개의 줄에 서비스를 통해 배달받는 정수가 한 줄에 하나씩 주어진다. 이 중 $i$번째 줄에 주어지는 수는 $V_i$이다.
$N$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 아인이가 $i$번째 날에 상품으로 선택할 수 있는 수를 하나 출력한다.
2 3 5
3 6
첫 번째 날에는 3ドル$이 배달된다. 아인이는 수를 선택하지 않고 0ドル$을 만들거나 배달받은 3ドル$을 선택해서 3ドル$을 만들 수 있는데, 0ドル$은 이진수로 표현해도 0ドル$이므로 3ドル$을 선택한다.
두 번째 날에는 5ドル$가 배달되고, 상품으로 줄 수 있는 새로운 후보로 5ドル$와 6ドル$($=3 \oplus 5$)이 생긴다. 이때 3ドル,ドル 5ドル,ドル 6ドル$이 모두 이진수로 표현할 때 1ドル$이 2ドル$개 등장하므로, 셋 중 어떤 것을 상품으로 선택해도 상관없다.
여기서 $\oplus$는 bitwise XOR 연산을 나타낸다.
3 6 14 9
6 14 15
첫 번째 날에는 6ドル$이 배달되고, 아인이는 위 예제의 첫 번째 날과 마찬가지로 배달받은 6ドル$을 선택해서 6ドル$을 만든다.
두 번째 날에는 14ドル$가 배달되고, 상품으로 줄 수 있는 새로운 후보로 14ドル$와 8ドル$($=6 \oplus 14$)이 생긴다. 네 가지 후보 중 14ドル$가 이진수로 표현할 때 1ドル$이 3ドル$개로 가장 많이 등장하므로, 아인이는 14ドル$를 상품으로 선택한다.
세 번째 날에는 9ドル$가 배달되고, 상품으로 줄 수 있는 새로운 후보로 9ドル,ドル 15ドル$($=6 \oplus 9$), 7ドル$($=14 \oplus 9$), 1ドル$($=6 \oplus 14 \oplus 9$)이 생긴다. 아인이는 총 8ドル$가지의 후보 중 이진수로 표현할 때 1ドル$이 4ドル$개 등장하는 유일한 수인 15ドル$를 상품으로 선택한다.
3 1010000000 110 1
1010000000 1010000110 1010000111