#P8984. [北大集训 2021] 末日魔法少女计划

[北大集训 2021] 末日魔法少女计划

题目背景

CTT2021 D1T1

题目描述

对于给定的 n,kn,k,你需要构造一个只含 0,10,1 的矩阵 Ai,jA_{i,j}0i,jn0\le i,j\le n,满足:

  1. Ai,i=1A_{i,i}=1
  2. Ai,i+1=1A_{i,i+1}=1
  3. i>ji>jAi,j=0A_{i,j}=0
  4. Ai,j=1A_{i,j}=1ji>1j-i>1,则存在 i<t<ji<t<j,满足 Ai,t=At,j=1A_{i,t}=A_{t,j}=1
  5. iji\le j(Ak)i,j>0(A^k)_{i,j}>0

你需要输出满足 Ai,j=1A_{i,j}=1ji>1j-i>1 的每个 (i,j)(i,j),设这样的 (i,j)(i,j) 共有 mm 个。

若输出不满足要求,则不能得到该测试点的任何分数。若输出满足要求,则根据 mm 进行评分。

输入格式

一行,两个整数 n,kn,k

输出格式

第一行一个整数 mm,接下来 mm 行,每行两个整数 i,ji,j,依次表示每个满足 Ai,j=1A_{i,j}=1ji>1j-i>1 的二元组 (i,j)(i,j)

3 2
1
0 2

提示

  • 1900n20001900\le n\le 2000
  • 2k152\le k\le 15
kk f(k)f(k) s(k)s(k)
22 7.98707.9870 2222
33 3.80853.8085 1414
44 2.39602.3960 1111
55 1.96101.9610 99
66 1.60651.6065 77
77 1.45151.4515 66
88 1.25401.2540 55
99 1.19801.1980 55
1010 1.09951.0995 44
1111 1.07051.0705 44
1212 1.03451.0345 44
1313 1.01201.0120 33
1414 1.00151.0015 33
1515 0.99400.9940 33

每个 2k152\le k\le 15 对应一个总分为 s(k)s(k) 的子任务,每个子任务的得分是子任务中每个测试点的得分的最小值。

每个测试点的得分为所在子任务的总分的 $\max\left(0,1-\sqrt{\max\left(0,\frac{m}{n\cdot f(k)}-1\right)}\right)$ 倍。