QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100
[+1]

# 3269. 末日魔法少女计划

Statistics

对于给定的 n,k,你需要构造一个只含 0,1 的矩阵 Ai,j0i,jn,满足:

  1. Ai,i=1
  2. Ai,i+1=1
  3. i>jAi,j=0
  4. Ai,j=1,ji>1,则存在 i<t<j,满足 Ai,t=At,j=1
  5. ij(Ak)i,j>0

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

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

输入格式

一行,两个整数 n,k

输出格式

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

样例数据

样例输入

3 2

样例输出

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

对于所有数据,1900n2000,2k15

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

每个测试点的得分为所在子任务的总分的 max 倍。