The Sum-XOR Dialogue

가능한 모든 정수 쌍을 그래프로 나타내자.

왼쪽에는 가능한 합 $s$마다 정점 $S_s$를 만든다. 오른쪽에는 가능한 XOR 값 $y$마다 정점 $Y_y$를 만든다. 가능한 쌍 $(a,b)$마다 $S_{a+b}$와 $Y_{a\mathbin{\mathrm{xor}}b}$를 잇는 간선을 하나 만든다.

어떤 날이 시작될 때 남아 있는 간선들은 이전 날까지의 모든 선언과 모순되지 않는 쌍들이다. 다다스가 관찰한 합에 대응하는 정점의 차수가 $1$이면 다다스는 두 수를 유일하게 알 수 있다. 모그도 같은 방식으로 XOR 정점의 차수가 $1$일 때 두 수를 알 수 있다.

두 사람은 동시에 말하므로, 한 날에는 시작 시점의 차수가 $1$인 정점에 닿은 모든 간선을 동시에 제거해야 한다. 따라서 정답은 실제 간선이 제거되는 라운드 번호이다. 끝까지 제거되지 않고 그래프의 $2$-core에 남으면 정답은 $-1$이다.

$X\ge 10$인 경우를 분석한다. $P$를 $X$ 이하의 가장 큰 $2$의 거듭제곱이라 하자.

합 정점의 초기 차수가 $1$인 경우는 다음 네 개뿐이다.

• 합이 $3$인 $(1,2)$.
• 합이 $4$인 $(1,3)$.
• 합이 $2X-2$인 .

초기 XOR 정점의 차수가 $1$인 경우는 다음과 같이 분류된다.

• $X=P$이면 $(i,P)$가 모든 $1\le i<P$에 대해 유일하다.
• $X=P+$이면 와 만 유일하다.

이를 보이기 위해 XOR 값 $y$를 생각하자. $y<P$이면 최상위 비트가 바뀌지 않는다. $P\ge 8$인 범위에서는 같은 XOR 값을 만드는 쌍을 낮은 구간에서 적어도 두 개 만들 수 있다.

$y\ge P$이면 $y=P+z$로 쓸 수 있다. 높은 쪽 수를 $P+t$라 하면 낮은 쪽 수는 $t$이다. 여기서 이다. 일 때만 낮은 쪽 수가 이 되어 사용할 수 없다.

• $X-P=0$이면 가능한 $t$가 하나뿐이므로 $(z,P)$가 유일하다.
• $X-P=1$이면 에서만 하나가 남고, 각각 과 이다.

이제 매 라운드에서 새로 차수가 $1$이 되는 정점을 조사하면 다음 표를 얻는다.

$X=P$일 때 첫 라운드에서 $(i,P)$가 모두 제거된다. 이 때문에 합 $2P-4$와 $2P-3$에서 각각 과 만 남아 둘째 날 제거된다.