U490727 返乡

# 返乡（home） ## 【题目背景】 "束の間 人を信じたら，もう半年がんばれる。" 每当小C回到那里时，都会想起当年被旧友7维偏序的恐惧。 又是一次考试失利，看着自己七科都比那位低的时候小C皱紧了眉头。 "但也没关系嘛，把 $121^7$ 种考试成绩取满，总会有一对被偏序的人嘛！"小C的伙伴安慰着他。 "不是的，我想肯定没必要有 $121^7$ 种成绩，就会产生偏序的！！"小C如是回答。 "唔，那到底有多少呢？" "\...\...先想想弱化版吧，先想想只有语数外三科的。" ## 【题目描述】 请问最多能有多少人，使得不存在一个人被另外一个人的成绩三维偏序，每科满分为 $n$，分数都是整数，并且可以爆零。 形式化的，找出最大的 $k$，使得存在一个三元组数组 $(a_1,b_1,c_1)\cdots (a_k,b_k,c_k)$ 满足 $0\le a_i,b_i,c_i\le n,a_i,b_i,c_i\in \mathbb{Z}$，且不存在点对 $i\not = j$,$a_i\le a_j,b_i\le b_j,c_i\le c_j$。 输出最大的 $k$,并给出构造，如有多种构造方式输出任意一种即可。 ## 【输入格式】 从文件 ***home.in*** 中读入数据。 输入一个正整数 $n$ 含义同题目描述。 ## 【输出格式】 输出到文件 ***home.out*** 中。 第一行输出一个整数 $k$，表示最大的人数。 接下来 $k$ 行，每行三个整数，表示这个人的每科成绩。 ## 【样例 1 输入】 1 ## 【样例 1 输出】 3 0 0 1 0 1 0 1 0 0 ## 【样例 2 输入】 2 ## 【样例 2 输出】 7 1 0 2 2 0 1 1 2 0 0 1 2 2 1 0 1 1 1 0 2 1 ## 【数据范围】 对于所有测试数据，保证 $1\le n\le 600$。 | 测试点编号 | $n\le$ | | ---------- | ------ | | $1\sim 2$ | $4$ | | $3\sim 5$ | $10$ | | $6\sim 7$ | $50$ | | $8\sim 10$ | $600$ |

无

无