P6020 [Ynoi2010] Exponential tree

Given $n, k$, you need to construct a matrix $A_{i,j}$ that only contains $0$ and $1$, where $0\le i,j\le n$, satisfying: 1. $A_{i,i}=1$. 2. $A_{i,i+1}=1$. 3. For $i>j$, $A_{i,j}=0$. 4. If $A_{i,j}=1$ and $j-i>1$, then there exists $i1$. Let there be $m$ such pairs $(i,j)$. If your output does not meet the requirements, you cannot get any score for that test point. If your output meets the requirements, then it will be scored based on $m$.

One line with two integers $n, k$.

The first line contains an integer $m$. The next $m$ lines each contain two integers $i, j$, representing each pair $(i,j)$ that satisfies $A_{i,j}=1$ and $j-i>1$, in order.

For $100\%$ of the testdata, $1900\le n\le 2000$ and $2\le k\le 15$. | $k$ | $f(n,k)$ | | ---- | -------- | | 2 | 7.987 | | 3 | 3.8085 | | 4 | 2.396 | | 5 | 1.961 | | 6 | 1.6065 | | 7 | 1.451 | | 8 | 1.2535 | | 9 | 1.1975 | | 10 | 1.099 | | 11 | 1.07 | | 12 | 1.034 | | 13 | 1.0115 | | 14 | 1.001 | | 15 | 0.994 | Each $2\le k\le 15$ corresponds to a subtask with total score $s(k)$. The score of each subtask is the minimum score among all test points in that subtask. For each test point, the score equals the subtask's total score multiplied by $\max\left(0,1-\sqrt{\max\left(0,\frac{m}{n\cdot f(k)}-1\right)}\right)$. Translated by ChatGPT 5