17696번 - Broken Device 점수다국어언어 제한함수 구현투 스텝피드백

문제

Anna and Bruno are archaeologists. They are investigating ruins in Iran.

Their tasks are as follows: Anna visits ruins and discovers artifacts, and Bruno analyzes the results in the base camp.

Their investigation is scheduled for Q(= 1 000) days. Every day, Anna sends the results to Bruno using a communication device. The results for each day is expressed as an integer X.

Anna can use the communication device once per day only. It can send a sequence of length N(= 150) consisting of 0 or 1.

However, it was broken. There are several broken places in the sequence of length N. For a broken place, it always sends the value 0 regardless of the actual set value. When Anna sends a sequence, she can see the positions of the broken places. But, Bruno does not know them. The positions of broken places and the number of broken places can change every day.

There is a danger that their investigation will be delayed. Because you are a candidate of a contestant of an international programming contest in Iran, Anna and Bruno ask you to write a program which sends the results of their investigation.

Write two programs which achieve the communication between Anna and Bruno.

• Given the length of the sequence N, the integer to be sent X, the number of broken places K, and the positions of broken places P, the first program sets the sequence S sent by Anna.
• Given the sequence A received by Bruno, the second program recovers the integer X.

At a place where the communication device works, the sequence S and the sequence A have the same value. At a broken place, the sequence A always has the value 0 regardless of the values of the sequence S .

구현

You need to submit two files written by the same programming language.

The first file is either Anna.c or Anna.cpp. This file sets a sequence sent by Anna, and implements the following function. The program should include Annalib.h.

• void Anna( int N, long long X, int K, int P[] )
  For each test case, this function is called Q = 1 000 times.
  • The parameter N is the length of the sequence to be sent.
  • The parameter X is the integer to be sent.
  • The parameter K is the number of broken places.
  • The parameter P[] is a sequence of length K, describing the positions of broken places.

In the function Anna, the following function must be called.

• void Set( int pos, int bit )
  This function sets a bit in the sequence S to be sent by the communication device.
  • The parameter pos is the position of the place to be set. pos must be an integer between 0 and N − 1, inclusive. Note that the positions are counted from 0. If it is called with parameter outside this range, your program is considered as Wrong Answer[1]. It is not allowed to call this function more than once with the same parameter pos. If it is called more than once with the same parameter, your program is considered as Wrong Answer[2].
  • The parameter bit is the value set to the pos-th position of the sequence. The value of bit must be either 0 or 1. If it is called with other parameters, your program is considered as Wrong Answer[3].

The function Set must be called exactly N times in the function Anna. When function Anna terminates, if the number of times the function Set is called is different from N, your program is considered as Wrong Answer[4].

Your program is terminated if the function call by Anna is considered invalid.

The second file is either Bruno.c or Bruno.cpp. This file recovers the integer expressing the results of investigation, and implements the following function. The program should include Brunolib.h.

• long long Bruno( int N, int A[] )
  For each test case, this function is called Q = 1 000 times.
  • The parameter N is the length of the sequence received by Bruno.
  • The parameter A is an integer sequence of length N. It is the sequence received by Bruno.
  • The function Bruno must recover the value of X, and return it.

입력

The sample grader reads the following data from the standard input.

• The first line contains an integer Q.
• Then, information of Q queries are given.
• Information of each query consists of two lines as follows.
  • The first line contains three space separated integers N, X, K. This means the length of the sequence to be sent is N, the integer to be sent by Anna is X, and there are K broken places.
  • The second line contains K space separated integers P₀, P₁, · · · , P_K−1. This means, for each i (0 ≤ i ≤ K − 1), the P_i-th place in the sequence is broken.

출력

When the program terminates successfully, the sample grader writes the following information to the standard output. (The quotation mark is not written actually.)

• If your program is considered as Wrong Answer, the sample grader writes its type in the following form “Wrong Answer [1],” and your program is terminated.
• If every function call to Anna is not considered as Wrong Answer, the sample grader writes “Accepted” and the value of L^∗. For the value of L^∗, see Scoring.

If your program is considered as several types of Wrong Answer, the sample grader reports only one of them.

제한

• Q = 1000.
• N = 150.
• 0 ≤ X ≤ 1 000 000 000 000 000 000.
• 1 ≤ K ≤ 40.
• 0 ≤ P_i ≤ N − 1 (0 ≤ i ≤ K − 1).
• P_i < P_i+1 (0 ≤ i ≤ K − 2).

점수

• Let L^∗ be the minimum of the following value for all test cases of this task.
  • The maximum integer L ≤ 40 such that, for every query with K ≤ L, Bruno answers the correct value of X.
• The score of this task is calculated by the following way:
  • If L^∗ = 0, the score is 0 point.
  • If 1 ≤ L^∗ ≤ 14, the score is 8 points.
  • If 15 ≤ L^∗ ≤ 37, the score is (L^∗ − 15) × 2 + 41 points.
  • If 38 ≤ L^∗ ≤ 40, the score is (L^∗ − 38) × 5 + 90 points.

힌트

예제

Here is a sample input for grader and corresponding function calls. Note that the following example does not satisfy the constraints of this task because Q = 2, N = 3.

2
3 14 1
2
3 9 2
0 1

Here the parameters for Anna(...), Bruno(...), Anna(...), Bruno(...) are as follows.

첨부

• dist.zip