32009번 - Magic Show 서브태스크다국어언어 제한함수 구현투 스텝

문제

Alice and Bob are famous magicians. Catherine, a wealthy woman who showed interest in their amazing deeds, declared that she would give them huge wealth if they could perform the following magic trick. The contents of the magic are as follows:

• Step 1ドル$: Bob enters a room and completely cuts off from the outside. Bob can only communicate with Catherine. Then, Alice tells Catherine a number $n$ between 2ドル$ and 5ドル,円 000$.
• Step 2ドル$: Catherine tells a number $X$ to Alice, which is between 1ドル$ and 10ドル^{18}$.
• Step 3ドル$: Alice makes a tree with exactly $n$ vertices, and gives it to Catherine.
• Step 4ドル$: Catherine deletes at most $\left\lfloor \frac{n-2}{2} \right\rfloor$ edges from the tree, and gives the remaining edges to Bob.
• Step 5ドル$: Bob carefully observes the graph, and tell the number which Catherine told to Alice.

However, Alice and Bob don't think they are smart enough to successfully perform this magic trick, so they are seeking your help. Please write a program which implements Alice’s strategy and Bob’s strategy so that they can beat Catherine’s challenge.

구현

You need to submit two files:

The first file is Alice.cpp, which implements Alice’s strategy. It should include Alice.h using the preprocessing directive #include. The function that needs to be implemented in the file is:

std::vector<std::pair<int, int>> Alice();

• For each test case, this function is called exactly once in the beginning.
• The function should return a vector of pairs, which represents the edges in the tree Alice constructed in Step 3ドル$ of the magic.
  • Note that the nodes of the tree should be numbered starting from 1ドル$.
  • You need to ensure that the returned tree is compliant, which means there should be exactly $n - 1$ edges and all nodes should be connected.

The function Alice() should call the following function exactly once:

long long setN(int n);

• Using this function, Alice chooses the parameter $n$ which she gave to Catherine in Step 1ドル$ of the magic.
• The function then returns the value $X,ドル which Catherine gave to Alice in Step 2ドル$ of the magic.

The second file is Bob.cpp, which implements Bob’s strategy. It should include Bob.h using the preprocessing directive #include. The function that needs to be implemented in the file is:

long long Bob(std::vector<std::pair<int, int>> V);

• For each test case, this function is called exactly once after the call of function Alice().
• The parameter $V$ is the list of edges of the graph Catherine gave to Bob in Step 4ドル$ of the magic.
• The edges are given in sorted order, which means:
  • For the two endpoints of each edge, the smaller numbered endpoint comes first;
  • All edges are sorted in ascending order based on the first endpoint being the first keyword and the second endpoint being the second keyword.
• The function should return a single integer, which represents the number $X$.

예제

It represents the following scenario:

• Step 1ドル$: At first, Alice gives 4ドル$ to Catherine.
• Step 2ドル$: Catherine gives 3ドル$ to Alice.
• Step 3ドル$: Alice makes a tree with 4ドル$ nodes and edges $\{\{1, 2\}, \{2, 3\}, \{2, 4\}\},ドル and tells it to Catherine.
• Step 4ドル$: Catherine cut the edge connecting nodes 2ドル$ and 3ドル,ドル and gives the remaining edges $\{\{1, 2\}, \{2, 4\}\}$ to Bob.
• Step 5ドル$: Bob tells the number 3ドル$. Because his answer is correct, they can successfully perform the magic show.

입력

출력

제한

• 1ドル ≤ X ≤ 10^{18}$.

서브태스크

힌트

샘플 그레이더

The sample grader reads the input in the following format:

• Line 1ドル$: $T$ ($T ∈ \{1, 2\}$)

if $T = 1,ドル then the sample grader reads as follows:

• Line 2ドル$: $X$ (1ドル ≤ X ≤ 10^{18}$)

The sample grader prints your answer of function Alice() in the following format:

• Line 1ドル$: $n$
• Line 2ドル + i$ (0ドル ≤ i ≤ n - 2$): $u[i]$ $v[i],ドル where there exists an edge connecting $u[i],ドル $v[i]$.

if $T = 2,ドル then The sample grader reads as follows:

• Line 2ドル$: $n$ $m$ (2ドル ≤ n ≤ 5000,ドル $n - 1 − \left\lfloor \frac{n-2}{2} \right\rfloor ≤ m ≤ n - 1$), where $n$ is number of vertices, and $m$ is number of remaining edges.
• Line 3ドル + i$ (0ドル ≤ i ≤ m - 1$): $u[i]$ $v[i],ドル which means there exists an edge connecting $u[i],ドル $v[i]$.

The sample grader prints your answer of function Bob() in the following format:

• Line 1ドル$: $X$

첨부

• Alice.cpp Alice.h Bob.cpp Bob.h compile_cpp.sh grader.cpp
• 1.in 1.out