P8984 [Peking University Training 2021] Doomsday Magical Girl Plan

CTT2021 D1T1

For given $n,k$, you need to construct a matrix $A_{i,j}$ that contains only $0,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 the number of such pairs be $m$. If your output does not meet the requirements, you will get no score for that test point. If your output meets the requirements, then you 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$, which represent each pair $(i,j)$ satisfying $A_{i,j}=1$ and $j-i>1$.

- $1900\le n\le 2000$. - $2\le k\le 15$. | $k$ | $f(k)$ | $s(k)$ | | :--: | :------: | :----: | | $2$ | $7.9870$ | $22$ | | $3$ | $3.8085$ | $14$ | | $4$ | $2.3960$ | $11$ | | $5$ | $1.9610$ | $9$ | | $6$ | $1.6065$ | $7$ | | $7$ | $1.4515$ | $6$ | | $8$ | $1.2540$ | $5$ | | $9$ | $1.1980$ | $5 $ | | $10$ | $1.0995$ | $4$ | | $11$ | $1.0705$ | $4 $ | | $12$ | $1.0345$ | $4$ | | $13$ | $1.0120$ | $3$ | | $14$ | $1.0015$ | $3 $ | | $15$ | $0.9940$ | $3$ | 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. The score of each test point equals the total score of its subtask multiplied by $\max\left(0,1-\sqrt{\max\left(0,\frac{m}{n\cdot f(k)}-1\right)}\right)$. Translated by ChatGPT 5