20093번 - Coins 서브태스크다국어언어 제한함수 구현투 스텝

문제

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:

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

• This procedure plays for Arnavaz.
• $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.
• $c$: label of the cell that contains the cursed coin.
• 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.

int find_coin(int[] b)

• This procedure plays for Shahrnaz.
• $b$: an integer array of length 64ドル,ドル demonstrating the chessboard that Zahhak presents to Shahrnaz (after Arnavaz has flipped some coins).
• It should return $c,ドル the position of the cursed coin.

There are $T$ scenarios. For each scenario, the grader calls the procedure coin_flips. Based on its returned value, the grader updates the chessboard and calls the procedure find_coin. Note that in the judging system these procedures are called in separate programs. In the first program, procedure coin_flips is called once for each scenario. Invocations of procedure find_coin 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.

입력

출력

제한

• 1ドル \leq T \leq 1000,ドル
• 0ドル \leq c \leq 63$.

예제

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:

coin_flips([0,0,...,0,0], 63)

In this example, $b$ is an array of length 64ドル$ filled with 0ドル$'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:

find_coin([0,0,...,0,1])

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

서브태스크

힌트

샘플 그레이더

The sample grader reads the input in the following format:

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

The sample grader writes the output in the following format:

• line 1ドル+i$ (for 0ドル \leq i \leq T-1$): the verdict of your solution for scenario $i$.

첨부

• coins.cpp
• coins.h
• grader.cpp
• 01.in