백준 20093 (C++) Coins

최초 업로드: 2025-10-11 15:24:48

최근 수정 시간: 2025-10-11 15:29:02

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] Coins

[문제 링크](https://www.acmicpc.net/problem/20093)

## 문제 설명

Zahhak, the enemy of Jamshid, has captured Jamshid's daughters, Arnavaz and Shahrnaz. But he decided to offer them an opportunity to free themselves by solving a puzzle.

Zahhak has an $8 \times 8$ chessboard with cells labeled from $0$ to $63$, as in the figure. He has put a coin on each of the $64$ cells. The cell with label $c$ has a special coin which is physically identical to the other coins, but it is cursed. Each coin is facing either heads or tails.

Zahhak invited the sisters to dinner to describe the puzzle: after the dinner, the sisters should go to different rooms. Then Zahhak goes to Arnavaz's room, presents her the chessboard and tells her the value of $c$ (the label of the cell containing the cursed coin). Arnavaz cannot change the position of the coins but can flip (turn over) at least $1$ and at most $k$ coins. She might flip the same coin several times. Then Zahhak goes to the other room and presents the chessboard to Shahrnaz. If she finds the cursed coin, both sisters will be freed. The sisters can agree on a strategy during the dinner, but cannot communicate afterward.

Your task is to help the sisters solve Zahhak's puzzle.

## 구현

You should implement two different procedures:

<pre>
<code>int[] coin_flips(int[] b, int c)
</code></pre>

<ul>
	<li>This procedure plays for Arnavaz.</li>
	<li>$b$: an integer array of length $64$, demonstrating the chessboard that Zahhak presents to Arnavaz. The value of $b[i]$ (for $0 \leq i \leq 63$) is either $0$ or $1$, which indicates the coin on cell $i$ is heads or tails, respectively.</li>
	<li>$c$: label of the cell that contains the cursed coin.</li>
	<li>It should return an array containing labels of the cells that Arnavaz flips their coins. Its length should be between $1$ and $k$, inclusive. It can contain a value more than once.</li>
</ul>

<ul>
	<li>This procedure plays for Shahrnaz.</li>
	<li>$b$: an integer array of length $64$, demonstrating the chessboard that Zahhak presents to Shahrnaz (after Arnavaz has flipped some coins).&nbsp;</li>
	<li>It should return $c$, the position of the cursed coin.</li>
</ul>

There are $T$ scenarios. For each scenario, the grader calls the procedure&nbsp;<code>coin_flips</code>. Based on its returned value, the grader updates the chessboard and calls the procedure&nbsp;<code>find_coin</code>. Note that in the judging system these procedures are called in separate programs. In the first program, procedure&nbsp;<code>coin_flips</code>&nbsp;is called once for each scenario. Invocations of procedure&nbsp;<code>find_coin</code>&nbsp;are made in the second program. The behavior of your implementation for each scenario must be independent of the order of the scenarios, as scenarios might not have the same order in the two programs.

## 제한

## 예제

Suppose the sisters decide that Arnavaz only flips the cursed coin and Shahrnaz reports the position of one of the coins with tails facing up, or $0$ if there is no such coin. Clearly, this is just an example, not a correct strategy.

The grader makes the following procedure call:

<pre>
<code>coin_flips([0,0,...,0,0], 63)
</code></pre>

In this example, $b$ is an array of length $64$ filled with $0$&#39;s which means all coins on the chessboard have heads facing up. This procedure returns an integer array of length $1$, containing a single value $[63]$.

Then the grader flips the coin in the cell number $63$ and makes the following procedure call:

This procedure returns $63$, and it is the correct position of the cursed coin.

## 서브테스크

## 샘플 그레이더

The sample grader reads the input in the following format:

<ul>
	<li>line $1$: $\;\;T$</li>
	<li>block $i$ (for $0 \leq i \leq T-1$): a block of $9$ lines, representing scenario $i$.
	<ul>
		<li>line $1$: $\;\;c$</li>
		<li>line $2+j$ (for $0 \leq j \leq 7$): a binary (<code>0</code>/<code>1</code>) string of length $8$ representing row $j$ of table $b$</li>
	</ul>
	</li>
</ul>

The sample grader writes the output in the following format:

<ul>
	<li>line $1+i$ (for $0 \leq i \leq T-1$): the verdict of your solution for scenario $i$.</li>
</ul>

## 첨부

<ul>
	<li><a href="https://upload.acmicpc.net/603d24c1-8d0c-4a42-bc74-cfb2504f742f/">coins.cpp</a></li>
	<li><a href="https://upload.acmicpc.net/9c4ea6ae-31a1-4654-81eb-a1d185645860/">coins.h</a></li>
	<li><a href="https://upload.acmicpc.net/6352bff3-d649-4c20-96c3-da98539874c1/">grader.cpp</a></li>
	<li><a href="https://upload.acmicpc.net/6361851d-59d5-4270-b75d-b982e045f317/">01.in</a></li>
</ul>

## 풀이
배열 b에서 1인 위치를 전부 XOR하면 임의의 6비트 이진수 하나가 나온다. 배열 b에서 1인 위치를 전부 XOR 했을 때, c가 나오게 하기 위해 이 나온 수를 c와 XOR한 위치의 동전을 (0이었다면 1로, 1이었다면 0으로) flip 해주면 된다. 이로 인해 배열을 받은 다음 사람은 배열 b에서 1인 위치를 전부 XOR하여 c의 위치를 알 수 있다.

``` c++
#include "coins.h"
using namespace std;

int getXor(vector<int> b) {
 int xorVal=0;
 for(int i=0;i<64;i++) {
 if(b[i]) xorVal ^= i;
 }
 return xorVal;
}

vector<int> coin_flips(vector<int> b, int c) {
 vector<int> flips(1);
 flips[0] = getXor(b)^c;
 return flips;
}

int find_coin(vector<int> b) {
 return getXor(b);
}
```