[IOI17] Coins

문제 : https://www.acmicpc.net/problem/20093

---

 

8×8 크기의 격자가 있다.

격자마다 동전이 하나씩 있다.

64개의 동전 중 앞면인 동전도 있고, 뒷면인 동전도 있다.

64개의 동전 중 저주받은 동전은 \(c\)이다.

 

 

 

저주받은 동전의 주인이 두 자매를 납치하였다.

그리고 언니에게만 \(c\)를 알려주고, 최소 1개에서 최대 \(k\)개의 동전을 뒤집을 수 있도록 하였다.

동생은 격자 상태를 보고 저주받은 동전 \(c\)를 찾는다면, 언니와 함께 납치범에게서 탈출 할 수 있다.

 

동생이 저주받은 동전 \(c\)를 찾는 문제.

 

구현해야 할 함수

int[] coin_flips(int[] b, int c)

b : 동전이 앞면인지 뒷면인지 나타내는 크기가 64인 배열

c : 저주받은 동전의 위치

언니가 뒤집을 동전의 인덱스 벡터를 반환한다.

언니는 동전 최소 하나는 뒤집어야 한다.

 

int find_coin(int[] b)

b : 언니가 동전을 뒤집은 후의 동전 상태

c를 반환해야 한다.

 

제약

• Subtask 1.(10점) c<2, k=1
• Subtask 2.(15점) c<3, k=1
• Subtask 3.(10점) k=64
• Subtask 4.(15점) k=8
• Subtask 5.(50점) k=1

 

---

풀이

Subtask 1.

\(c\)가 0 또는 1이므로, 0이 \(c\)인지 아닌지만 표시하면 된다.

 

---

 

Subtask 2.

\(c\)가 0 또는 1 또는 2이다.

000\(_{(2)}\)~111\(_{(2)}\) 중, \(c\)번째 비트가 나머지 두 비트와 parity가 다르게 세팅하면 된다.

만약 \(c\)가 1이라면, 010\(_{(2)}\) 또는 101\(_{(2)}\) 중 가능한 모양을 만들면 된다.

 

---

 

Subtask 3.

\(k=64\)이므로, \(c\)위치만 다른 모양으로 만들면 된다.

 

---

 

Subtask 4.

\(k=8\)이지만, 6개의 동전만으로 \(c\)의 위치를 비트로 나타낼 수 있다.

 

---

 

Subtask 5.

 

만점은 동전 하나만 뒤집어야 하는데 XOR연산을 사용한다.

 

동전이 앞면인 곳의 인덱스를 \(a\)라고 할 때, 모든 \(a\)를 XOR한다.

• \(a_0 \bigoplus a_1 \bigoplus \cdots \bigoplus a_{m-1} \)
• \(m\)은 앞면인 동전의 개수다.
• \(m\)이 0이면, XOR 결과는 0이다.

 

\(a\)와 \(c\)의 XOR 결과를 \(f\)라고 하자.

$$ f = a_0 \bigoplus a_1 \bigoplus \cdots \bigoplus a_{m-1} \bigoplus c $$

 

언니는 \(f\)번째 동전만 뒤집으면 된다.

이 때, \(f\)는 \(0 \le f < 64\)를 만족한다.

 

동생은 격자 정보를 받으면, 언니와 마찬가지로 앞면인 동전마다 XOR 연산을 한다.

동생의 XOR 결과는 \(a_0 \bigoplus a_1 \bigoplus \cdots \bigoplus a_{m-1} \bigoplus c \bigoplus f\)이다.

 

그런데 \(f = a_0 \bigoplus a_1 \bigoplus \cdots \bigoplus a_{m-1} \)이므로,

\(a_0 \bigoplus a_1 \bigoplus \cdots \bigoplus a_{m-1} \bigoplus c \bigoplus f = f \bigoplus c \bigoplus f = c\)가 된다.

 

즉 동생은 앞면인 동전만 XOR하여 \(c\)를 구할 수 있다.