#B. 关门捉贼

    传统题 文件IO:guan 1000ms 256MiB

关门捉贼

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小敌困之。剥,不利有攸往。

题目描述

33DAI 发现有 nn 只小猫在 m×mm\times m 的二维数组里,第 ii 只小猫在第 xix_i 行的第 yiy_i 列(保证 2xi,yim12\le x_i,y_i\le m-1),可能有多只小猫在同一个位置。

已知每只小猫都只会往上下左右四个方向直线行走,不会拐弯。33DAI 可以在某些位置放稻草人来拦住小猫。稻草人必须放在 m×mm\times m 的二维数组内,且不能放在已经有小猫或稻草人的位置。请帮 33DAI 构造一个放稻草人的方案。

形式化的说,如果在

  • xix_i 行的第 1yi11\sim y_i-1
  • xix_i 行的第 yi+1my_i+1\sim m
  • yiy_i 列的第 1xi11\sim x_i-1
  • yiy_i 列的第 xi+1mx_i+1\sim m

这四个区域都分别至少放了一个稻草人,就可以拦住第 ii 只小猫。

输入格式

第一行两个整数 n,mn,m

接下来 nn 行,第 ii 行为两个整数 xi,yix_i,y_i

输出格式

显然不可能无解,最多 4×n4\times n 个稻草人肯定能拦住所有小猫,如果有多解,输出任意一种即可。

第一行需要输出一个 14×n1\sim 4\times n 范围内的整数 kk,表示需要放 kk 个稻草人。

接下来 kk 行,第 ii 行为第 ii 个稻草人的位置 ui,viu_i,v_i,即放在第 uiu_i 行的第 viv_i 列。

3 5
2 2
2 4
4 4
7
1 2
1 4
2 1
2 5
4 2
4 5
5 4

输出为一种可能的方案,下面是这个方案放稻草人的位置

数据规模与约定

对于 100%100\% 的数据,1n5001 \le n \le 5003m1093\le m\le 10^92xi,yim12\le x_i,y_i\le m-1

  • 子任务 1(10 分):保证 m=3m=3
  • 子任务 2(20 分):保证 n=1n=1
  • 子任务 3(30 分):保证 14×(m1)161\le 4\times (m-1)\le 16
  • 子任务 4(40 分):没有特殊限制。

挖土机 CSP-J 模拟赛 ~ 第十二场

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-10-7 4:00
结束于
2024-10-9 4:00
持续时间
3.5 小时
主持人
参赛人数
79