P11058 Merge Bananas


There are $n$ bananas. The $i$-th banana can be simplified as a positive integer pair $(a_i,k_i)$, where $2\le k_i\le 10$. Initially, there are $n$ piles of bananas, and the $i$-th pile contains only the $i$-th banana. Each time, you may choose two different piles to merge. During a merge, the sizes of bananas will be reduced. Specifically, if the $i$-th banana **participates in a merge**, then its size $a_i$ becomes $\frac{1}{k_i}$ of its original value. **Participates in a merge**: before merging, it is in one of the two piles being merged. You want to merge all bananas into one pile. Since bigger bananas are better, you need to make the sum of all $a_i$ after all operations **as large as possible**. Considering that finding the optimal solution may be difficult, you only need to get **as close to the standard answer as possible**. See the **Scoring** section for details. To prevent you from outputting a random number, you also need to **output a plan**. See the **Output Format** section for details.

The first line contains one positive integer $n$. The next $n$ lines each contain two positive integers $a_i,k_i$.

Output $n-1$ lines. Each line contains two numbers $x,y$, meaning to merge pile $x$ and pile $y$. For the $i$-th merge, denote the newly formed pile as pile $n+i$. The two original piles (pile $x$ and pile $y$) will henceforth **be considered nonexistent**, so you are not allowed to use $x$ and $y$ in later merges. Otherwise, you will get zero points.

### Sample Explanation For the sample, the given output corresponds to ending with $a=(0.01,3,16)$, and the sum of $a_i$ is $19.01$. Also, if you output the following, then it ends with $a=(0.01,9,8)$, and the sum of $a_i$ is $17.01$, which can get $4$ points. ``` 1 3 2 4 ``` ### Scoring For each test point, scoring is done as follows: - If your output is invalid, you get $0$ points. - Otherwise, let $f$ be the sum of $a_i$ after all operations for your output plan, and let $ans$ be the sum of $a_i$ after all operations for the standard answer’s plan. Your score is $s=\lfloor \max\{0,10-\log_{10} \max\{1,\frac{ans-f}{\epsilon}\}\}\rfloor$ points, where $\epsilon=10^{-5}$. ### Constraints This problem has $10$ test points, each worth $10$ points. | Test Point ID | $n=$ | Special Property | | :----------: | :----------: | :----------: | | $1$ | $3$ | None | | $2$ | $5$ | None | | $3$ | $10$ | None | | $4$ | $20$ | None | | $5$ | $100$ | None | | $6$ | $10^3$ | None | | $7$ | $10^5-3$ | $a_i=1$ and $k_i=2$ | | $8$ | $10^5-2$ | $a_i=1$ | | $9$ | $10^5-1$ | $k_i=2$ | | $10$ | $10^5$ | None | For all data, it is guaranteed that $3\le n\le 10^5$, $1\le a_i\le 10^5$, and $2\le k_i\le 10$. Translated by ChatGPT 5