对于给定的 n,k,你需要构造一个只含 0,1 的矩阵 Ai,j,0≤i,j≤n,满足:
- Ai,i=1。
- Ai,i+1=1。
- 对 i>j 有 Ai,j=0。
- 若 Ai,j=1,j−i>1,则存在 i<t<j,满足 Ai,t=At,j=1。
- 对 i≤j 有 (Ak)i,j>0。
你需要输出满足 Ai,j=1 且 j−i>1 的每个 (i,j),设这样的 (i,j) 共有 m 个。
若输出不满足要求,则不能得到该测试点的任何分数。若输出满足要求,则根据 m 进行评分。
输入格式
一行,两个整数 n,k。
输出格式
第一行一个整数 m,接下来 m 行,每行两个整数 i,j,依次表示每个满足 Ai,j=1 且 j−i>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 |
对于所有数据,1900≤n≤2000,2≤k≤15。
每个 2≤k≤15 对应一个总分为 s(k) 的子任务,每个子任务的得分是子任务中每个测试点的得分的最小值。
每个测试点的得分为所在子任务的总分的 max 倍。