#564. 「LibreOJ Round #10」613 的天网

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 613

题目描述

有一个 n\times n\times n 的三维矩阵,需要在若干个格子中放置摄像头。

一个摄像头的拍摄范围是它所在的一行,一列以及一纵列(即可以往 6 个方向看,同时也能看到自己)。

目标是使得这个矩阵不存在摄像头看不到的位置。

构造一种方案,使得摄像头数量尽量少。

输入格式

第一行一个正整数 n 表示这个三维矩阵的边长为 n

输出格式

第一行一个正整数 t 表示你的方案中摄像头的个数。

接下来 t 行,每行三个在 [1,n] 中的整数 x,\,y,\,z 表示一个摄像头的坐标。

样例

样例输入

2

样例输出

2
1 1 1
2 2 2

数据范围与提示

对于所有数据, 1\leq n\leq 2000

本题设有部分分,对于一个测试点,若你的答案为 x 且方案合法,你将获得以下比例的得分:

rate=\begin{cases} 1 & x<\lceil 0.5n^2\rceil \\ 1 & x=\lceil 0.5n^2\rceil \\ 0.8\times(\frac{\lceil 0.5n^2\rceil}{x})^3 & x>\lceil 0.5n^2\rceil \end{cases}

对于任意一个子任务,你的得分为其所有测试点得分的最小值。

子任务编号 分值 n \leq 特殊限制
1 10 10 -
2 50 n 为偶数
3 n 为奇数
4 15 300 n 为偶数
5 n 为奇数
6 20 2000 n 为偶数
7 n 为奇数

注意:如果你的方案不够优,输出会非常庞大,建议使用必要的输出优化。