{"raw_statement":[{"iden":"background","content":"CTT2021 D1T1"},{"iden":"statement","content":"对于给定的 $n,k$，你需要构造一个只含 $0,1$ 的矩阵 $A_{i,j}$，$0\\le i,j\\le n$，满足：\n\n1. $A_{i,i}=1$；\n2. $A_{i,i+1}=1$；\n3. 对 $i>j$ 有 $A_{i,j}=0$；\n4. 若 $A_{i,j}=1$，$j-i>1$，则存在 $i<t<j$，满足 $A_{i,t}=A_{t,j}=1$；\n5. 对 $i\\le j$ 有 $(A^k)_{i,j}>0$。\n\n你需要输出满足 $A_{i,j}=1$ 且 $j-i>1$ 的每个 $(i,j)$，设这样的 $(i,j)$ 共有 $m$ 个。\n\n若输出不满足要求，则不能得到该测试点的任何分数。若输出满足要求，则根据 $m$ 进行评分。\n"},{"iden":"input","content":"一行，两个整数 $n,k$。\n"},{"iden":"output","content":"第一行一个整数 $m$，接下来 $m$ 行，每行两个整数 $i,j$，依次表示每个满足 $A_{i,j}=1$ 且 $j-i>1$ 的二元组 $(i,j)$。"},{"iden":"note","content":"- $1900\\le n\\le 2000$；\n- $2\\le k\\le 15$。\n\n| $k$  |  $f(k)$  | $s(k)$ |\n| :--: | :------: | :----: |\n| $2$  | $7.9870$ |  $22$  |\n| $3$  | $3.8085$ |  $14$  |\n| $4$  | $2.3960$ |  $11$  |\n| $5$  | $1.9610$ |  $9$   |\n| $6$  | $1.6065$ |  $7$   |\n| $7$  | $1.4515$ |  $6$   |\n| $8$  | $1.2540$ |  $5$   |\n| $9$  | $1.1980$ |  $5 $   |\n| $10$ | $1.0995$ |  $4$   |\n| $11$ | $1.0705$ |  $4 $   |\n| $12$ | $1.0345$ |  $4$   |\n| $13$ | $1.0120$ |  $3$   |\n| $14$ | $1.0015$ |  $3 $   |\n| $15$ | $0.9940$ |  $3$   |\n\n\n\n每个 $2\\le k\\le 15$ 对应一个总分为 $s(k)$ 的子任务，每个子任务的得分是子任务中每个测试点的得分的最小值。\n\n每个测试点的得分为所在子任务的总分的 $\\max\\left(0,1-\\sqrt{\\max\\left(0,\\frac{m}{n\\cdot f(k)}-1\\right)}\\right)$ 倍。\n"}],"translated_statement":null,"sample_group":[["3 2","1\n0 2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}