시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 1024 MB32266.667%

문제

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:

Percentage $P_C$ $C$
$100$ $ =1 $
$60$ $ \leq 3 $
$15$ $ \leq 17 $
$10$ $ \leq 34 $
$0$ $ >34 $

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:

Percentage $P_L$ $L$
$100$ $ \leq 10 $
$10$ $ \leq 30$
$0$ $ >30$
Percentage $P_L$ $L$
$100$ $ \leq 16 $
$100-\frac{L-16}{50-16}\times 20$ $ \leq 50 $
$80-(\frac{L-50}{2000-50})^{0.4}\times 35$ $ \leq 2000 $
$45-(\frac{L-2000}{50000-2000})^{0.3}\times 40$ $ \leq 50\ 000$
$0$ $ > 50\ 000$

$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:

Percentage $P_L$ $L$
$100$ $ \leq 152 $
$100-(\frac{L-152}{260-152})^{0.5}\times 15$ $ \leq 260 $
$85-\frac{L-260}{290-260}\times 10$ $ \leq 290 $
$75-(\frac{L-290}{550-290})^{0.3}\times 10$ $ \leq 550$
$65-(\frac{L-550}{2000-550})^{0.6}\times 20$ $ \leq 2000 $
$45-(\frac{L-2000}{50000-2000})^{0.3}\times 40$ $ \leq 50\ 000$
$0$ $ > 50\ 000$

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$

서브태스크

Subtasks Points Required subtasks $T$ Additional constraints
1 40 $=1$
2 10 1 $=2$ The indices of the two Reni's pictures are consecutive numbers.
3 50 1, 2 $\leq 2$

예제

Participant’s function Jury’s program
play(6, 1)
guess({ {1,2,3}, {4,5,6} }) 10
guess({ {1}, {2}, {3} }) 010
return {2} Correct!
Participant’s function Jury’s program
play(6, 2)
guess({ {1,2}, {3,4}, {5,6} }) 011
guess({ {3}, {5} }) 01
return {5,4} Correct!

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.

제출할 수 있는 언어

C++17, C++20, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.