#2052. 末日魔法少女计划
末日魔法少女计划
末日魔法少女计划
题目描述
标题: 末日魔法少女计划 - Problem - QOJ.ac
#3269. 末日魔法少女计划
The problem was used in the following contests:
对于给定的 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(0,1−max(0,mn⋅f(k)−1)) 倍。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 2
1
0 2