#2052. 末日魔法少女计划

    ID: 2052 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest869来源:qoj.ac数据:公开样例贪心枚举

末日魔法少女计划

末日魔法少女计划

题目描述

标题: 末日魔法少女计划 - Problem - QOJ.ac

#3269. 末日魔法少女计划

Statistics

The problem was used in the following contests:

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

  1. Ai,i=1。
  2. Ai,i+1=1。
  3. 对 i>j 有 Ai,j=0。
  4. 若 Ai,j=1,j−i>1,则存在 i<t<j,满足 Ai,t=At,j=1。
  5. 对 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