XOR 섬

시간 제한3초메모리 제한1024 MB

요약

모자 숫자 n개가 주어졌을 때, 자신의 숫자가 XOR 삼중항에 속한다는 것을 처음 알아내는 날을 구합니다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 해시맵, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

완벽한 논리학자만 사는 섬이 있다. 각 섬사람은 양의 정수가 적힌 모자를 쓰고 있다. 섬사람은 다른 모든 사람의 모자에 적힌 수를 볼 수 있지만, 자기 모자의 수는 볼 수 없다. 섬사람은 자기 모자의 수가 양의 정수라는 사실 외에는 그 수에 대해 아는 것이 없다.

어느 날 하늘에 신비한 메시지가 나타난다. "서로 다른 세 섬사람이 있어서, 그중 두 사람의 모자에 적힌 수의 XOR이 나머지 한 사람의 모자에 적힌 수와 같다." 메시지가 나타난 뒤, 섬사람들은 연달아 며칠 동안 하루에 한 번씩 회의를 연다. 회의마다 메시지를 만족하는 세 사람 중 한 명에 속한다고 확실히 아는 섬사람은 손을 든다.

섬사람은 거짓말을 하거나 실수하지 않으며, 자신이 세 사람 중 하나에 속한다고 알 수 있게 되는 즉시 손을 든다. 회의에서 적어도 한 명이 손을 들 때까지 며칠이 걸리는지 구하시오.

입력

첫 줄에 섬사람의 수를 나타내는 정수 $n$ ( $3 \le n \le 25$ )이 주어진다.

다음 $n$ 개 줄에는 각각 섬사람 한 명의 모자에 적힌 양의 정수 $a$ ( $1 \le a < 2^{25}$ )가 하나씩 주어진다.

입력은 하늘의 메시지가 참이 되도록 주어진다. 즉, 모자의 수 중에 한 수가 나머지 두 수의 XOR과 같은 세 수가 적어도 하나 있다.

출력

섬사람 중 누군가가 자신의 모자가 XOR 세 수의 일부임을 알아내기까지 걸리는 회의 날짜 수를 정수 하나로 출력한다. 결국 적어도 한 명은 손을 든다는 것을 증명할 수 있다.

예제2

예제 1
입력
```
3
1
2
3
```
예상 출력
```
1
```
예제 2
입력
```
11
9
1
14
2
11
7
6
7
6
5
3
```
예상 출력
```
3
```