B. 613 的天网

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

题目描述

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

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

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

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

输入格式

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

输出格式

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

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

样例

样例输入

2

样例输出

2
1 1 1
2 2 2

数据范围与提示

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

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

rate={1x<0.5n21x=0.5n20.8×(0.5n2x)3x>0.5n2rate=\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}

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

子任务编号 分值 nn \leq 特殊限制
1 1010 1010 -
2 1010 5050 nn 为偶数
3 1010 5050 nn 为奇数
4 1515 300300 nn 为偶数
5 1515 300300 nn 为奇数
6 2020 20002000 nn 为偶数
7 2020 20002000 nn 为奇数

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