32491번 - TWINS 서브태스크점수다국어언어 제한함수 구현

문제

Once again, the twins Reni and Nora managed to fool everybody by switching places. Alex was convinced that he had figured out a strategy for telling them apart. But it turns out he was wrong. Reni and Nora, knowing that he is hopelessly confused, decide to try one of their newly invented games. It consisted of the following:

They choose $N$ different pictures of themselves, numbered from 1ドル$ to $N,ドル one or two of which are of Reni and the rest are of Nora. Alex is allowed to ask questions like: "Among the pictures with numbers $p_1,\ p_2,\ ...\ p_K\ (1 \leq K \leq N),ドル is there at least one picture of Reni?". However, to make it more interesting, he can submit a whole group with several such questions and receive the answers to each of them at the same time.

The purpose of the game for Alex is to guess which pictures are of Reni and which are of Nora after some finite number of questions (which in itself would be an achievement for him), but also to minimize both the number of question groups and the total number of questions in them. He needs your help for this. Write a program twins that finds the required one or two pictures.

Write a program twins that, determines which of the pictures are of Reni and which are of Nora. It must contain the function play that will be compiled with the jury's program.

구현 상세

Your function play must have the following format:

std::vector<int> play (int N, int T);

It will be called only once during one execution of the program with two parameters: the number of pictures $N$ and the number of Reni's pictures - $T\ ( T\in \{1,2\} )$. The function should return the indices of the one or two Reni's pictures. Their order does not matter.

For communication with the jury's program you should use the following function:

std::string guess (std::vector< std::vector<int> >& questions);

As a parameter, it receives a group of questions, each containing a set of picture numbers. For example, if Alex wants to ask 2ドル$ questions and the first one is about the pictures 1ドル$ and 2ドル,ドル and the second one is about the pictures 2ドル$ and 3ドル,ドル it should be given $\{\ \{1,2\},\ \{2,3\}\ \}$. It is allowed to have "empty"{} questions that ask nothing (passing $\{ \{\ \},\ \{2,3\}\ \}$ as a parameter). They will not count towards the total number of questions used.

The function returns a string composed of 0ドル$ and 1ドル,ドル indicating "no" and "yes" answers to the questions, respectively. Suppose you asked $M$ questions in a group. They are numbered with the numbers 0ドル$ through $M-1$ in the order in which you submitted them, and correspond to the indices of answers in the string.

You must submit to the system a file twins.cpp that contains the function play. It can also contain other code, functions, and global variables, but it must not contain the main function. Also, you should not read from the standard input or print to the standard output. Your program must include the header file twins.h by instruction to the preprocessor:

#include "twins.h"

점수

Each test receives a score that is a fractional number between 0 and 1 inclusive. If a test has a positive score, it is considered a successful test for your solution. Because Nora and Reni encourage even suboptimal games, they use the following scoring system.

Let $C$ be the number of calls to the function guess. The evaluation with respect to $C$ for all tests is as follows:

Let $L$ be the total number of questions you used across all calls to the guess function.

$T = 1$인 경우 점수

When $T=1$ there are two types of tests. In the first $N\in [15,30]$ (the first table), and in the second $N=50\ 000$ (the second table). The evaluation with respect to $L$ in tests when $T=1$ is as follows:

$T = 2$인 경우 점수

When $T=2$ in all tests $N=50\ 000$. The evaluation with respect to $L$ in tests when $T=2$ is as follows:

If you make an invalid action or do not guess the pictures correctly, you will get score 0ドル$ for the test. Otherwise, the score is equal to $P_C \times P_L$. For example, on a test with $T=2,ドル if $L = 2000$ and $P = 3,ドル your score will be 45ドル\% \times 60\% = 0.27$.

입력

출력

제한

• 15ドル \leq N \leq 50\ 000$
• 1ドル \leq T \leq 2$

서브태스크

힌트

예제

Let's look at the first example. After the first two questions which are asked at once, we know that the requested picture is among the first 3ドル$. Similarly, with the last 3ドル$ questions, we find out exactly which one it is.

로컬 테스팅로

The file Lgrader.cpp is provided for local testing. Put your twins.cpp file together with Lgrader.cpp and twins.h into one folder and compile the three files together. This will give you a program to check the correctness of your function. The program will require two numbers on the first line $-$ $N$ and $T$. On the next line the program requires the numbers of the pictures that are of Reni. The program will display in detail the steps when performing this test. To change this, you can change the value of the DETAILS constant at the beginning of the code. You can modify this file as you wish.

첨부

• Lgrader.cpp twins.cpp twins.h