UOJ Logo Universal Online Judge

UOJ

#709. 【北大集训2021】末日魔法少女计划

附件下载 统计

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

  1. $A_{i,i}=1$。
  2. $A_{i,i+1}=1$。
  3. 对 $i\gt j$ 有 $A_{i,j}=0$。
  4. 若 $A_{i,j}=1,j-i\gt 1$,则存在 $i\lt t\lt j$,满足 $A_{i,t}=A_{t,j}=1$。
  5. 对 $i\le j$ 有 $(A^k)_{i,j}\gt 0$。

你需要输出满足 $A_{i,j}=1$ 且 $j-i\gt 1$ 的每个 $(i,j)$,设这样的 $(i,j)$ 共有 $m$ 个。

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

输入格式

从标准输入读入数据。

一行,两个整数 $n,k$。

输出格式

输出到标准输出。

第一行一个整数 $m$,接下来 $m$ 行,每行两个整数 $i,j$,依次表示每个满足 $A_{i,j}=1$ 且 $j-i\gt 1$ 的二元组 $(i,j)$。

样例

input

3 2

output

1
0 2

数据范围与提示

$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

对于所有数据,$1900\le n\le 2000, 2\le k\le 15$。

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

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

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$